Kosaraju

From Algowiki
Jump to navigation Jump to search

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 DFS trees are the strongly connected components.

Correctness

Complexity

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

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