Kosaraju: Difference between revisions
Jump to navigation
Jump to search
| Line 10: | Line 10: | ||
# Invert the output order of the nodes. | # Invert the output order of the nodes. | ||
# Let <math>G'=(V,A')</math> be the [[Basic graph definitions|transpose]] of <math>G=(V,A)</math>. | # Let <math>G'=(V,A')</math> be the [[Basic graph definitions|transpose]] of <math>G=(V,A)</math>. | ||
# Apply a [[repeated depth-first search]] to <math>G'</math> with a modification: The nodes are considered as start nodes in the inverted order | # Apply a [[repeated depth-first search]] to <math>G'</math> with a modification: The nodes are considered as start nodes in the inverted order from step 2. | ||
# The DFS trees are the strongly connected components. | # The DFS trees are the strongly connected components. | ||
Revision as of 13:03, 10 October 2014
General information
Algorithmic problem: Strongly connected components
Type of algorithm: loop
Abstract View
- Apply a repeated depth-first search to [math]\displaystyle{ G }[/math].
- Invert the output order of the nodes.
- Let [math]\displaystyle{ G'=(V,A') }[/math] be the transpose of [math]\displaystyle{ G=(V,A) }[/math].
- 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.
- 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.