Kosaraju: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 8: | Line 8: | ||
# Apply a [[repeated depth-first search]] to <math>G</math>. | # Apply a [[repeated depth-first search]] to <math>G</math>. | ||
# Let <math>G'</math> be the [[transpose]] of <math>G</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 | # Apply a [[repeated depth-first search]] to <math>G'</math> with a modification: The nodes are considered as start nodes | ||
# The DFS trees are the strongly connected components. | # The DFS trees are the strongly connected components. | ||
== Correctness == | == Correctness == | ||
Revision as of 13:01, 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].
- 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
- 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.