Kosaraju

General information

Algorithmic problem: Strongly connected components

Type of algorithm: loop

Abstract View

1. Apply a repeated depth-first search to [math]\displaystyle{ G }[/math].
2. Invert the output order of the nodes.
3. Let [math]\displaystyle{ G'=(V,A') }[/math] be the transpose of [math]\displaystyle{ G=(V,A) }[/math].
4. Apply a repeated depth-first search to [math]\displaystyle{ G' }[/math] with a modification: The nodes are considered as start nodes in the inverted order from step 2.
5. The node sets from the applications of DFS inside step 4 are exactly the SCC of [math]\displaystyle{ G }[/math].

Correctness

First note that the transposition of all arcs does not change the SCC of a graph, so step 4 indeed processes the SCC of [math]\displaystyle{ G }[/math].

Let [math]\displaystyle{ C_1,\ldots,C_k }[/math] denote the SCC of [math]\displaystyle{ G }[/math]. Consider the condensed graph whose nodes are these SCC, and there is an arc from [math]\displaystyle{ C_i }[/math] to [math]\displaystyle{ C_j }[/math] if, and only if, there is an arc in [math]\displaystyle{ G }[/math] from some node in [math]\displaystyle{ C_i }[/math] to some node in [math]\displaystyle{ C_j }[/math]. This condensed graph is acyclic because all nodes in all SCC on a cycle are mutually reachable from each other in [math]\displaystyle{ G }[/math].

In step 1, each DFS run either meets all nodes of an SCC of [math]\displaystyle{ G }[/math] or none of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC in the condensed graph, except for the SCC processed in previous DFS runs.

It is easy to see that all nodes of an SCC are finished consecutively; that is, all nodes of an SCC form a connected subsequence in the output sequence of step 1. In particular, it does not matter in step 4 which node of an SCC is chosen as a start node for a DFS run. If an SCC [math]\displaystyle{ C_i }[/math] is reachable from an SCC [math]\displaystyle{ C_j }[/math] in [math]\displaystyle{ G }[/math], then the nodes of [math]\displaystyle{ C_i }[/math] appear before the nodes of [math]\displaystyle{ C_j }[/math] in that order. Equivalently, the nodes of [math]\displaystyle{ C_i }[/math] appear after the nodes of [math]\displaystyle{ C_j }[/math] in the reverse order.

Let [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math] be two SCC of [math]\displaystyle{ G }[/math]. Since each SCC is processed exhaustively or not at all in a DFS run, it suffices to show that [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math] are not processed within the same run. Suppose for a contradiction that [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math] are processed in the same DFS run in step 4 (not necessarily in the same run in step 1). Let [math]\displaystyle{ CK }[/math] be the SCC to which the start node of that run belongs (possibly [math]\displaystyle{ k=i }[/math] or [math]\displaystyle{ k=j }[/math]). Without loss of generality, suppose [math]\displaystyle{ k\neq i }[/math]. Then [math]\displaystyle{ C_i }[/math] is reachable from [math]\displaystyle{ C_k }[/math] in [math]\displaystyle{ G' }[/math]; in other words, [math]\displaystyle{ C_k }[/math] is reachable from [math]\displaystyle{ C_i }[/math] in [math]\displaystyle{ G }[/math]. However, then the nodes of [math]\displaystyle{ C_i }[/math] have higher finishing times than the nodes of [math]\displaystyle{ C_k }[/math], so some node of [math]\displaystyle{ C_i }[/math] had been chosen as a start node before any node of [math]\displaystyle{ C_k }[/math].

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(|V|+|A|) }[/math].

Proof: Follows immediately from the linear asymptotic complexity of DFS.