In: Computer Science
Write an algorithm to determine if the directed graph is strongly connected or not
Answer) Checking if a graph is strongly connected using Kosaraju’s DFS based simple algorithm that does two DFS traversals of graph:
1) Initialize all vertices as they are not visited.
2) Do the DFS traversal of the graph starting from any arbitrary vertex v. If the DFS traversal does not visit all the vertices then return false.
3) Reverse all arcs (or find transpose).
4) Mark all vertices as not-visited in the reversed graph.
5) Do a DFS traversal of the reversed graph starting from same vertex v (Same as step 2). If the DFS traversal does not visit all the vertices then return false. Otherwise, return true.
The idea is that if every node can be reached from 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 the step 4, we check if all vertices can reach v (In the reversed graph, if all vertices are reachable from v, then all vertices can reach v in the original graph).