Kosaraju
Revision as of 18:06, 8 October 2014 by Weihe (talk | contribs) (Created page with "== General information == '''Algorithmic problem:''' Strongly connected components '''Type of algorithm:''' loop == Abstract View == # Apply a repeated depth-first...")
General information
Algorithmic problem: Strongly connected components
Type of algorithm: loop
Abstract View
- Apply a repeated depth-first search to [math]\displaystyle{ G }[/math].
- Let [math]\displaystyle{ G' }[/math] be the transpose of [math]\displaystyle{ G }[/math].
- Apply a repeated depth-first search to [math]\displaystyle{ G' }[/math] with a modification: The nodes are
- 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.