Algorithm to check if directed graph is strongly c

Question

I need to check if a directed graph is strongly connected, or, in other words, if all nodes can be reached by any other node (not necessarily through direct edge).

One way of doing this is running a DFS and BFS on every node and see all others are still reachable.

Is there a better approach to do that?

Answer 1

Consider the following algorithm.

---

1. Start at a random vertex v of the graph G, and run a DFS(G, v).

   • If DFS(G, v) fails to reach every other vertex in the graph G, then there is some vertex u, such that there is no directed path from v to u, and thus G is not strongly connected.

   • If it does reach every vertex, then there is a directed path from v to every other vertex in the graph G.

2. Reverse the direction of all edges in the directed graph G.

3. Again run a DFS starting at v.

   • If the DFS fails to reach every vertex, then there is some vertex u, such that in the original graph there is no directed path from u to v.

   • On the other hand, if it does reach every vertex, then in the original graph there is a directed path from every vertex u to v.

Thus, if G "passes" both DFSs, it is strongly connected. Furthermore, since a DFS runs in O(n + m) time, this algorithm runs in O(2(n + m)) = O(n + m) time, since it requires 2 DFS traversals.

Answer 2

Tarjan's Algorithm has been already mentioned. But I usually find Kosaraju's Algorithm easier to follow even though it needs two traversals of the graph. IIRC, it is also pretty well explained in CLRS.