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 fro step 2.
5. The DFS trees are the strongly connected components.

Complexity

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

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