{"id":26343,"date":"2017-10-26T21:09:54","date_gmt":"2017-10-26T15:39:54","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26343"},"modified":"2018-10-29T12:11:01","modified_gmt":"2018-10-29T06:41:01","slug":"java-programming-find-path-two-vertices-directed-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-find-path-two-vertices-directed-graph\/","title":{"rendered":"Find if there is a path between two vertices in a directed graph"},"content":{"rendered":"

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

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 in our traversal, then return true. Else return false.<\/p>\n

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

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

Java\u00a0Programming to Find if there is a path between two vertices in a directed graph:<\/span><\/h3>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20check%20if%20there%20is%20exist%20a%20path%20between%20two%20vertices%0A%2F%2F%20of%20a%20graph.%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0Aimport%20java.util.LinkedList%3B%0A%20%0A%0Aclass%20Graph%0A%7B%0A%20%20%20%20private%20int%20V%3B%20%20%20%0A%20%20%20%20private%20LinkedList%3CInteger%3E%20adj%5B%5D%3B%20%0A%20%0A%0A%20%20%20%20Graph(int%20v)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20V%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20adj%20%3D%20new%20LinkedList%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cv%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20adj%5Bi%5D%20%3D%20new%20LinkedList()%3B%0A%20%20%20%20%7D%0A%20%0A%0A%20%20%20%20void%20addEdge(int%20v%2Cint%20w)%20%20%7B%20%20%20adj%5Bv%5D.add(w)%3B%20%20%20%7D%0A%20%0A%20%20%20%0A%20%20%20%20Boolean%20isReachable(int%20s%2C%20int%20d)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%3CInteger%3Etemp%3B%0A%20%0A%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20boolean%20visited%5B%5D%20%3D%20new%20boolean%5BV%5D%3B%0A%20%0A%20%20%20%0A%20%20%20%20%20%20%20%20LinkedList%3CInteger%3E%20queue%20%3D%20new%20LinkedList%3CInteger%3E()%3B%0A%20%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20visited%5Bs%5D%3Dtrue%3B%0A%20%20%20%20%20%20%20%20queue.add(s)%3B%0A%20%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20i%3B%0A%20%20%20%20%20%20%20%20while%20(queue.size()!%3D0)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20s%20%3D%20queue.poll()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20n%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20adj%5Bs%5D.listIterator()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(i.hasNext())%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%20n%20%3D%20i.next()%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(n%3D%3Dd)%0A%20%20%20%20%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%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(!visited%5Bn%5D)%0A%20%20%20%20%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%20%20%20%20%20visited%5Bn%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20queue.add(n)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%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%0A%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20Graph%20g%20%3D%20new%20Graph(4)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(0%2C%202)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(1%2C%202)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(2%2C%200)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(2%2C%203)%3B%0A%20%20%20%20%20%20%20%20g.addEdge(3%2C%203)%3B%0A%20%0A%20%20%20%20%20%20%20%20int%20u%20%3D%201%3B%0A%20%20%20%20%20%20%20%20int%20v%20%3D%203%3B%0A%20%20%20%20%20%20%20%20if%20(g.isReachable(u%2C%20v))%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22There%20is%20a%20path%20from%20%22%20%2B%20u%20%2B%22%20to%20%22%20%2B%20v)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22There%20is%20no%20path%20from%20%22%20%2B%20u%20%2B%22%20to%20%22%20%2B%20v)%3B%3B%0A%20%0A%20%20%20%20%20%20%20%20u%20%3D%203%3B%0A%20%20%20%20%20%20%20%20v%20%3D%201%3B%0A%20%20%20%20%20%20%20%20if%20(g.isReachable(u%2C%20v))%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22There%20is%20a%20path%20from%20%22%20%2B%20u%20%2B%22%20to%20%22%20%2B%20v)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22There%20is%20no%20path%20from%20%22%20%2B%20u%20%2B%22%20to%20%22%20%2B%20v)%3B%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/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=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Java 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":31628,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,78385,73906,2139],"tags":[78426,78421,78420,78419,78424,78423,78417,78425],"class_list":["post-26343","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-coding","category-connectivity","category-graph-algorithms","category-java","tag-bfs-find-all-paths","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-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26343","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=26343"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26343\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31628"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26343"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26343"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26343"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}