Correctness of Strongly Connected Components algorithm for a directed graph

Question

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?

Answer 1

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 strong component 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.

Answer 2

My understanding:

When you execute DFS on any DAG graph keeping track of the finishing times, the only thing you can guarantee is that sink node will never get the highest finishing time [1]. But at the same time, the lowest finishing time may appear in any component of the graph. Hence, it makes the lowest finishing time kind of useless.

Basically, the fact [1] is useless in the original graph as well, but it is very useful in the transposed graph. When you transpose, this statement leads to the following:

In the transposed graph, the node that was a sink in the non-transposed graph will always get the highest finishing time.

Answer 3

1. strongly connected components in $G$ and $G_{transpose}$ will remain the same (implied by definition of strongly connected components)

2. any graph can be divided into strongly connected components - let's call these components $C_1, C_2, C_3 \dots C_N$

After first round of DFS and sorting in descending order of finish time

Let's say the component $C_i$ has the node with highest finish time. One tricky thing to observe that this component $C_i$ which has highest finish time cannot have any outside edge coming into the component $C_i$.

To prove the above fact (by contradiction):-
let's consider that there exists a component $C_j$ from which there is an edge into component $C_i$.
And $C_j$ has no node which has larger finish time than $C_i$'s node -

but this is not possible because during DFS $C_j$ will have then larger finish time. (Even if you start DFS from any node - you can check by yourself.)

Now you have component $C_i$ and no outside edge is coming inside $C_i$ so if you transpose the graph the components will not change (because strongly connected) but the edges connecting them will be reversed.

Therefore $C_i$ have no edge going out to other components. That's all we wanted;
if you apply DFS on this graph starting from any node of $C_i$ you will traverse only through this $C_i$ component and will not enter into others.

This way you have separated $C_i$ from graph.

Hope that helped,
comment if you have any doubt, I'll try to reply asap