{"id":26345,"date":"2017-10-26T21:10:21","date_gmt":"2017-10-26T15:40:21","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26345"},"modified":"2018-10-31T14:54:18","modified_gmt":"2018-10-31T09:24:18","slug":"python-programming-find-path-two-vertices-directed-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-find-path-two-vertices-directed-graph\/","title":{"rendered":"Find if there is a path between two vertices in a directed graph"},"content":{"rendered":"

Find if there is a path between two vertices in a directed graph<\/strong><\/span><\/p>\n

Given a Directed Graph<\/a> and two vertices in it, check whether there is a path from the first given vertex to second. <\/span>For example, in the following graph, there is a path from vertex 1 to 3. As another example, there is no path from 3 to 0.<\/p>\n

\"directed-graph\"<\/p>\n

We can either use Breadth First Search<\/a> (BFS) or Depth First Search<\/a> (DFS) to find path between two vertices. Take the first vertex as source in BFS (or DFS), follow the standard BFS (or DFS). If we see the second vertex<\/a> in our traversal, then return true. Else return false.<\/p>\n

Following is Python code<\/a> that use BFS for finding reachability of second vertex from first vertex.<\/p>\n

Python\u00a0Programming\u00a0Find if there is a path between two vertices in a directed graph:<\/strong><\/span><\/h4>\n
<\/div> 
# program to check if there is exist a path between two vertices# of a graph from collections import defaultdict  #This class represents a directed graph using adjacency list representationclass Graph:      def __init__(self,vertices):        self.V= vertices #No. of vertices        self.graph = defaultdict(list) # default dictionary to store graph      # function to add an edge to graph    def addEdge(self,u,v):        self.graph[u].append(v)         # Use BFS to check path between s and d    def isReachable(self, s, d):        # Mark all the vertices as not visited        visited =[False]*(self.V)          # Create a queue for BFS        queue=[]          # Mark the source node as visited and enqueue it        queue.append(s)        visited[s] = True          while queue:             #Dequeue a vertex from queue             n = queue.pop(0)                         # If this adjacent node is the destination node,            # then return true            if n == d:                return True             #  Else, continue to do BFS            for i in self.graph[n]:                if visited[i] == False:                    queue.append(i)                    visited[i] = True        # If BFS is complete without visited d        return False  # Create a graph given in the above diagramg = 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 =1; v = 3 if g.isReachable(u, v):    print("There is a path from %d to %d" % (u,v))else :    print("There is no path from %d to %d" % (u,v)) u = 3; v = 1if g.isReachable(u, v) :    print("There is a path from %d to %d" % (u,v))else :    print("There is no path from %d to %d" % (u,v))<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
 There is a path from 1 to 3\r\n There is no path from 3 to 1<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python Programming – Find if there is a path between two vertices in a directed graph – check whether there is a path from the first given vertex to second. <\/p>\n","protected":false},"author":1,"featured_media":31290,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,78385,73906,4148],"tags":[78421,78420,78419,78424,78423,78428,78417,78427],"class_list":["post-26345","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-coding","category-connectivity","category-graph-algorithms","category-python","tag-find-all-paths-between-two-nodes-in-a-graph-c","tag-find-all-paths-between-two-nodes-in-a-graph-java","tag-find-all-paths-from-source-to-destination","tag-find-all-paths-from-source-to-destination-java","tag-find-all-paths-in-a-directed-graph","tag-find-all-possible-paths-between-two-points-in-a-matrix","tag-find-all-possible-paths-between-two-vertices-on-a-graph","tag-graph-check-if-path-exists"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26345","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26345"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26345\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31290"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26345"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26345"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26345"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}