{"id":26411,"date":"2017-12-20T21:18:39","date_gmt":"2017-12-20T15:48:39","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26411"},"modified":"2017-12-20T21:18:39","modified_gmt":"2017-12-20T15:48:39","slug":"java-programming-check-graph-strongly-connected-set-1-kosaraju-using-dfs","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-check-graph-strongly-connected-set-1-kosaraju-using-dfs\/","title":{"rendered":"JAVA programming – Check if a graph is strongly connected"},"content":{"rendered":"

Given a directed graph, find out whether the graph is strongly connected or not. A directed graph is strongly connected if<\/span> there is a path between any two pair of vertices. For example, following is a strongly connected graph.<\/p>\n

It is easy for undirected graph<\/strong>, we can just do a BFS and DFS starting from any vertex. If BFS or DFS visits all vertices, then the given undirected graph is connected. This approach won\u2019t work for a directed graph. For example, consider the following graph which is not strongly connected. If we start DFS (or BFS) from vertex 0, we can reach all vertices, but if we start from any other vertex, we cannot reach all vertices.<\/p>\n

How to do for directed graph?<\/strong>
\nA simple idea is to use a all pair shortest path algorithm like Floyd Warshall<\/a> or find Transitive Closure<\/a><\/strong> of graph. Time complexity of this method would be O(v3<\/sup>).<\/p>\n

We can also do DFS <\/a>V times<\/strong> starting from every vertex. If any DFS, doesn\u2019t visit all vertices, then graph is not strongly connected. This algorithm takes O(V*(V+E)) time which can be same as transitive closure for a dense graph.<\/p>\n

A better idea can be Strongly Connected Components (SCC)<\/a> algorithm<\/strong>. We can find all SCCs in O(V+E) time. If number of SCCs is one, then graph is strongly connected. The algorithm for SCC does extra work as it finds all SCCs.<\/p>\n[ad type=\u201dbanner\u201d]\n

Following is Kosaraju\u2019s DFS based simple algorithm that does two DFS traversals<\/strong> of graph:
\n1)<\/strong> Initialize all vertices as not visited.<\/p>\n

2)<\/strong> Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn\u2019t visit all vertices, then return false.<\/p>\n

3)<\/strong> Reverse all arcs (or find transpose or reverse of graph)<\/p>\n

4)<\/strong> Mark all vertices as not-visited in reversed graph.<\/p>\n

5)<\/strong> Do a DFS traversal of reversed graph starting from same vertex v (Same as step 2). If DFS traversal doesn\u2019t visit all vertices, then return false. Otherwise return true.<\/p>\n

The idea is, if every node can be reached from a vertex v, and every node can reach v, then the graph is strongly connected. In step 2, we check if all vertices are reachable from v. In step 4, we check if all vertices can reach v (In reversed graph, if all vertices are reachable from v, then all vertices can reach v in original graph).<\/p>\n[ad type=\u201dbanner\u201d]\n

JAVA PROGRAMMING<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20check%20if%20a%20given%20directed%20graph%20is%20strongly%0A%2F%2F%20connected%20or%20not%0Aimport%20java.io.*%3B%0Aimport%20java.util.*%3B%0Aimport%20java.util.LinkedList%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20directed%20graph%20using%20adjacency%0A%2F%2F%20list%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20private%20int%20V%3B%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%20%20%20private%20LinkedList%3CInteger%3E%20adj%5B%5D%3B%20%2F%2FAdjacency%20List%0A%20%0A%20%20%20%20%2F%2FConstructor%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%20%20%20%20%2F%2FFunction%20to%20add%20an%20edge%20into%20the%20graph%0A%20%20%20%20void%20addEdge(int%20v%2Cint%20w)%20%7B%20%20adj%5Bv%5D.add(w)%3B%20%7D%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20to%20print%20DFS%20starting%20from%20v%0A%20%20%20%20void%20DFSUtil(int%20v%2CBoolean%20visited%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%20and%20print%20it%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20int%20n%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20i%20%3D%20adj%5Bv%5D.iterator()%3B%0A%20%20%20%20%20%20%20%20while%20(i.hasNext())%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20n%20%3D%20i.next()%3B%0A%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%20DFSUtil(n%2Cvisited)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Function%20that%20returns%20transpose%20of%20this%20graph%0A%20%20%20%20Graph%20getTranspose()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Graph%20g%20%3D%20new%20Graph(V)%3B%0A%20%20%20%20%20%20%20%20for%20(int%20v%20%3D%200%3B%20v%20%3C%20V%3B%20v%2B%2B)%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%20Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20%20%20%20%20Iterator%3CInteger%3E%20i%20%3D%20adj%5Bv%5D.listIterator()%3B%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%20%20%20%20g.adj%5Bi.next()%5D.add(v)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20g%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20The%20main%20function%20that%20returns%20true%20if%20graph%20is%20strongly%0A%20%20%20%20%2F%2F%20connected%0A%20%20%20%20Boolean%20isSC()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%201%3A%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20%20%20%20%20%2F%2F%20(For%20first%20DFS)%0A%20%20%20%20%20%20%20%20Boolean%20visited%5B%5D%20%3D%20new%20Boolean%5BV%5D%3B%0A%20%20%20%20%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%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%202%3A%20Do%20DFS%20traversal%20starting%20from%20first%20vertex.%0A%20%20%20%20%20%20%20%20DFSUtil(0%2C%20visited)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20DFS%20traversal%20doesn\u2019t%20visit%20all%20vertices%2C%20then%0A%20%20%20%20%20%20%20%20%2F%2F%20return%20false.%0A%20%20%20%20%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%20%20%20%20%20if%20(visited%5Bi%5D%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%203%3A%20Create%20a%20reversed%20graph%0A%20%20%20%20%20%20%20%20Graph%20gr%20%3D%20getTranspose()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%204%3A%20Mark%20all%20the%20vertices%20as%20not%20visited%20(For%0A%20%20%20%20%20%20%20%20%2F%2F%20second%20DFS)%0A%20%20%20%20%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%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%205%3A%20Do%20DFS%20for%20reversed%20graph%20starting%20from%0A%20%20%20%20%20%20%20%20%2F%2F%20first%20vertex.%20Staring%20Vertex%20must%20be%20same%20starting%0A%20%20%20%20%20%20%20%20%2F%2F%20point%20of%20first%20DFS%0A%20%20%20%20%20%20%20%20gr.DFSUtil(0%2C%20visited)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20all%20vertices%20are%20not%20visited%20in%20second%20DFS%2C%20then%0A%20%20%20%20%20%20%20%20%2F%2F%20return%20false%0A%20%20%20%20%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%20%20%20%20%20if%20(visited%5Bi%5D%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%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%2F%2F%20Create%20graphs%20given%20in%20the%20above%20diagrams%0A%20%20%20%20%20%20%20%20Graph%20g1%20%3D%20new%20Graph(5)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(1%2C%202)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(2%2C%203)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(3%2C%200)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(2%2C%204)%3B%0A%20%20%20%20%20%20%20%20g1.addEdge(4%2C%202)%3B%0A%20%20%20%20%20%20%20%20if%20(g1.isSC())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%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(%22No%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20Graph%20g2%20%3D%20new%20Graph(4)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(0%2C%201)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(1%2C%202)%3B%0A%20%20%20%20%20%20%20%20g2.addEdge(2%2C%203)%3B%0A%20%20%20%20%20%20%20%20if%20(g2.isSC())%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Yes%22)%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(%22No%22)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n\n\n\n
\n
\n
<\/code><\/code><\/div>\n
\n

Output:<\/p>\n

Yes\r\nNo<\/pre>\n[pastacode lang=\u201djava\u201d manual=\u201dJAVA%20programming-Check%20if%20a%20graph%20is%20strongly%20connected%20%7C%20Set%201%20(Kosaraju%20using%20DFS)\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<\/div>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
JAVA programming-Check if a graph is strongly connected | Set 1 (Kosaraju using DFS)-find out whether the graph is strongly connected or not<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,78385,73906,2139],"tags":[78756,78755,78422,78754,78751,78750,78753,78752],"class_list":["post-26411","post","type-post","status-publish","format-standard","hentry","category-coding","category-connectivity","category-graph-algorithms","category-java","tag-c-program-to-check-the-connectivity-of-undirected-graph-using-bfs","tag-check-if-graph-is-connected-adjacency-matrix","tag-check-if-path-exists-between-two-nodes","tag-check-if-undirected-graph-is-connected","tag-connected-graph-examples","tag-strongly-connected-graph-example","tag-strongly-connected-undirected-graph","tag-weakly-connected-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26411","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=26411"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26411\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26411"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26411"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26411"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}