{"id":26333,"date":"2017-10-26T21:06:37","date_gmt":"2017-10-26T15:36:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26333"},"modified":"2017-10-26T21:06:37","modified_gmt":"2017-10-26T15:36:37","slug":"find-path-two-vertices-directed-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-path-two-vertices-directed-graph\/","title":{"rendered":"C Programming &#8211; Find if there is a path between two vertices in a directed graph"},"content":{"rendered":"<p>Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second. <span id=\"more-18750\"><\/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<p>We can either use Breadth First Search (BFS) or Depth First Search (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 in our traversal, then return true. Else return false.<\/p>\n<p>Following are C++,Java and Python codes that use BFS for finding reachability of second vertex from first vertex.<\/p>\n<p>C++ Programming<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20check%20if%20there%20is%20exist%20a%20path%20between%20two%20vertices%0A%2F%2F%20of%20a%20graph.%0A%23include%3Ciostream%3E%0A%23include%20%3Clist%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20directed%20graph%20using%20adjacency%20list%20%0A%2F%2F%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%20%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20list%3Cint%3E%20*adj%3B%20%20%20%20%2F%2F%20Pointer%20to%20an%20array%20containing%20adjacency%20lists%0Apublic%3A%0A%20%20%20%20Graph(int%20V)%3B%20%20%2F%2F%20Constructor%0A%20%20%20%20void%20addEdge(int%20v%2C%20int%20w)%3B%20%2F%2F%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20bool%20isReachable(int%20s%2C%20int%20d)%3B%20%20%0A%7D%3B%0A%20%0AGraph%3A%3AGraph(int%20V)%0A%7B%0A%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20adj%20%3D%20new%20list%3Cint%3E%5BV%5D%3B%0A%7D%0A%20%0Avoid%20Graph%3A%3AaddEdge(int%20v%2C%20int%20w)%0A%7B%0A%20%20%20%20adj%5Bv%5D.push_back(w)%3B%20%2F%2F%20Add%20w%20to%20v%E2%80%99s%20list.%0A%7D%0A%20%0A%2F%2F%20A%20BFS%20based%20function%20to%20check%20whether%20d%20is%20reachable%20from%20s.%0Abool%20Graph%3A%3AisReachable(int%20s%2C%20int%20d)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20if%20(s%20%3D%3D%20d)%0A%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20bool%20*visited%20%3D%20new%20bool%5BV%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20queue%20for%20BFS%0A%20%20%20%20list%3Cint%3E%20queue%3B%0A%20%0A%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%20and%20enqueue%20it%0A%20%20%20%20visited%5Bs%5D%20%3D%20true%3B%0A%20%20%20%20queue.push_back(s)%3B%0A%20%0A%20%20%20%20%2F%2F%20it%20will%20be%20used%20to%20get%20all%20adjacent%20vertices%20of%20a%20vertex%0A%20%20%20%20list%3Cint%3E%3A%3Aiterator%20i%3B%0A%20%0A%20%20%20%20while%20(!queue.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Dequeue%20a%20vertex%20from%20queue%20and%20print%20it%0A%20%20%20%20%20%20%20%20s%20%3D%20queue.front()%3B%0A%20%20%20%20%20%20%20%20queue.pop_front()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Get%20all%20adjacent%20vertices%20of%20the%20dequeued%20vertex%20s%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20a%20adjacent%20has%20not%20been%20visited%2C%20then%20mark%20it%20visited%0A%20%20%20%20%20%20%20%20%2F%2F%20and%20enqueue%20it%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%20adj%5Bs%5D.begin()%3B%20i%20!%3D%20adj%5Bs%5D.end()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20this%20adjacent%20node%20is%20the%20destination%20node%2C%20then%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20return%20true%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(*i%20%3D%3D%20d)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Else%2C%20continue%20to%20do%20BFS%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!visited%5B*i%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited%5B*i%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20queue.push_back(*i)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20If%20BFS%20is%20complete%20without%20visiting%20d%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20methods%20of%20graph%20class%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%20%20%20Graph%20g(4)%3B%0A%20%20%20%20g.addEdge(0%2C%201)%3B%0A%20%20%20%20g.addEdge(0%2C%202)%3B%0A%20%20%20%20g.addEdge(1%2C%202)%3B%0A%20%20%20%20g.addEdge(2%2C%200)%3B%0A%20%20%20%20g.addEdge(2%2C%203)%3B%0A%20%20%20%20g.addEdge(3%2C%203)%3B%0A%20%0A%20%20%20%20int%20u%20%3D%201%2C%20v%20%3D%203%3B%0A%20%20%20%20if(g.isReachable(u%2C%20v))%0A%20%20%20%20%20%20%20%20cout%3C%3C%20%22%5Cn%20There%20is%20a%20path%20from%20%22%20%3C%3C%20u%20%3C%3C%20%22%20to%20%22%20%3C%3C%20v%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20cout%3C%3C%20%22%5Cn%20There%20is%20no%20path%20from%20%22%20%3C%3C%20u%20%3C%3C%20%22%20to%20%22%20%3C%3C%20v%3B%0A%20%0A%20%20%20%20u%20%3D%203%2C%20v%20%3D%201%3B%0A%20%20%20%20if(g.isReachable(u%2C%20v))%0A%20%20%20%20%20%20%20%20cout%3C%3C%20%22%5Cn%20There%20is%20a%20path%20from%20%22%20%3C%3C%20u%20%3C%3C%20%22%20to%20%22%20%3C%3C%20v%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20cout%3C%3C%20%22%5Cn%20There%20is%20no%20path%20from%20%22%20%3C%3C%20u%20%3C%3C%20%22%20to%20%22%20%3C%3C%20v%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre> There is a path from 1 to 3\r\n There is no path from 3 to 1<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C Programming &#8211; Find if there is a path between two vertices in a directed graph &#8211; check whether there is a path from the first given vertex to second. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,82927,1,78385,73906],"tags":[78422,78421,78420,78419,78424,78423,78417,78418],"class_list":["post-26333","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-2","category-coding","category-connectivity","category-graph-algorithms","tag-check-if-path-exists-between-two-nodes","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-vertices-on-a-graph","tag-find-path-between-two-nodes-in-a-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26333","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=26333"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26333\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}