Correctness of Strongly Connected Components algorithm for a directed graph

Problem Detail: 

I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$.

The algorithm is the following :

1. Execute DFS on $G$ (starting at an arbitrary starting vertex), keeping track of the finishing times of all vertices.
2. Compute the transpose,
3. Execute DFS on $G^T$, starting at the vertex with the latest finishing time, forming a tree rooted at that vertex. Once a tree is completed, move on to the unvisited vertex with the next latest finishing time and form another tree using DFS and repeat until all the vertices in $G^T$ are visited.
4. Output the vertices in each tree formed by the second DFS as a separate strongly connected component.

My question is :

1. What is the intuition behind this middle step of computing a transpose?

Asked By : Geek

Answered By : Raphael

Transposing the adjecency matrix $A$ does

$\qquad A[i,j] = 1 \iff A^T[j,i] = 1$.

In terms of graphs, that means

$\qquad u \to_G v \iff v \to_{G^T} u$.

In other words, transposing reverses the direction of all edges. Note that $G^T$ has the same strong components as $G$.

The algorithm you are looking at is Kosaraju's algorithm. Be carful with your notion of "finishing time": it's not the time the node is visited, but when the search has traversed the subgraph reachable from it. Wikipedia proposes to use a stack to manage this, which I think is a good idea.

Why is it correct to use $G^T$, intuitively? Assume $x$ is the first node of its strong component visited by the DFS.

• The DFS on $G$ traverses the whole strong component of $x$ after reaching $x$, plus some others via edges that leave the component.
• Since we use a stack order for remembering the order of nodes, $x$ is also the first node of its subcomponent visited (as starting node, even) in the second phase.
• Since $G$ and $G^T$ have the same strong components, all nodes in the strong component of $x$ are visited when searching $G^T$ from $x$. Those edges leaving the component in the first phase point in the wrong direction in $G^T$ and are thus not followed. All edges leaving the component of $x$ in $G^T$ have already been removed because of the stack order.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11232