Write Python program for checking whether a given graph G has simple path from source s to destination d. Assume the graph G is represented using adjacent matrix.

Code:

 

from collections import defaultdict

class Graph:

    def __init__ (self,vertices):

        self.V=vertices

        self.graph=defaultdict(list)

    def addEdge(self,u,v):

        self.graph[u].append(v)

    def isReachable(self,s,d):

        visited=[False]*(self.V)

        queue=[]

 

        queue.append(s)

        visited[s]=True

 

        while queue:

            n=queue.pop(0)

 

            if n==d:

                return True

            for i in self.graph[n]:

                if visited[i]==False:

                     queue.append(i)

                     visited[i]=True

        return False

g=Graph(4)

g.addEdge(0,1)

g.addEdge(0,2)

g.addEdge(1,2)

g.addEdge(2,0)

g.addEdge(2,3)

g.addEdge(3,3)

u=2;v=1

if g.isReachable(u,v):

    print("There is path from %d to %d" %(u,v))

else:

    print("There is no path from %d to %d" %(u,v))

u=1;v=2

if g.isReachable(u,v):

    print("There is path from %d to %d" %(u,v))

else:

    print("There is no path from %d to %d" %(u,v))

O/p:-

6(B).

from collections import defaultdict

class Graph:

    def __init__(self):

        self.graph=defaultdict(list)

    def addEdge(self,u,v):

        self.graph[u].append(v)

    def DFSUtil(self,v,visited):

        visited[v]=True

        print(v)

        for i in self.graph[v]:

            if visited[i]==False:

                self.DFSUtil(i,visited)

    def DFS(self,v):

        visited=[False]*(len(self.graph))

        self.DFSUtil(v,visited)

 

g=Graph()

g.addEdge(0,1)

g.addEdge(0,2)

g.addEdge(1,2)

g.addEdge(2,0)

g.addEdge(2,3)

g.addEdge(3,3)

 

print("Following is DFS from (Starting from vertex 2)")

g.DFS(1)

O/p:

Fundamental of algorithm