Kosaraju: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== General information == '''Algorithmic problem:''' Strongly connected components '''Type of algorithm:''' loop == Abstract View == # Apply a repeated depth-first...") |
No edit summary |
||
| Line 4: | Line 4: | ||
'''Type of algorithm:''' loop | '''Type of algorithm:''' loop | ||
== Abstract View == | == Abstract View == | ||
| Line 12: | Line 11: | ||
# 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 | ||
# The DFS trees are the strongly connected components. | # The DFS trees are the strongly connected components. | ||
== Correctness == | == Correctness == | ||
== Complexity == | == Complexity == | ||
Revision as of 12:54, 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' }[/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.