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

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]. Obviously, this condensed graph is acyclic because any two nodes of [math]\displaystyle{ G }[/math] in the SCC on such a cycle are mutually reachable from each other in [math]\displaystyle{ G }[/math].

In step 1, each application of DFS either meets all nodes of an SCC of [math]\displaystyle{ G }[/math]or none of its nodes. 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 met in previous applications of DFS.

In the transpose of [math]\displaystyle{ G }[/math], the SCC of the start node

Complexity

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

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