Logic(Correctness) behind Strongly Connected Components Algorithm (Application of DFS)

Question

"A Directed graph is said to be strongly connected if every vertex is reachable from every other vertex".

The Algorithm given in the Coreman is as follows :-

STRONGLY-CONNECTED-COMPONENTS (G)

 1. Call DFS(G) to compute finishing times f[u] for all u.
 2. Compute GT
 3. Call DFS(GT), but in the main loop, consider vertices in order of decreasing f[u] (as computed in first DFS)
 4. Output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC.

I tried to understand the correctness of this algorithm, and logic behind Step 3, but didn't get that. Please help me to undertand this, give me the feel behind this.

I read some answers on SO, but didn't give me proper feel. So please explain logically, with example. Thanks in advance.

Answer 1

Here is explanation of the algorithm :-

1. Finishing times :- The SCC's can be visualized single nodes and we can form a graph from them. The graph formed by SCC's are always DAG(Directed Acyclic Graph) where there is a source vertex and a sink vertex as if the graph has a cycle then the nodes in cycle will combine into a single SCC. The SCC that forms a source will have only outgoing edges whereas sink has only incoming edges. By that logic you can deduce that the SCC's that are closer to source will have higher finish times and closer to sink will have lower finish times.

2. Transpose:- When you take the transpose of graph the source becomes the sink and sink becomes the source but the SCC's of the graph remain unchanged only their cycles are reversed.

3. DFS:- We start calculating the DFS on nodes that have higher finishing times which were in SCC's closer to the source in original graph. First we start with SCC which was source in the original but now it is the sink. Now we know that sink has no outgoing edges hence we evaluate DFS on it we only visit nodes that are part of that SCC hence when we can group them into one. When First SCC is visited the SCC that has only outgoing edge to it now becomes the new sink which would have second highest finishing time in original graph so now we can do DFS to get its components.

For more clarity you can search for Kosaraju's SCC algorithm