7
$\begingroup$

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?
$\endgroup$
9
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.