Kosaraju: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 8: Line 8:


# Apply a [[repeated depth-first search]] to <math>G</math>.
# Apply a [[repeated depth-first search]] to <math>G</math>.
# 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
# Apply a [[repeated depth-first search]] to <math>G'</math> with a modification: The nodes are considered as start nodes in the inverted order fro step 2.
# The DFS trees are the strongly connected components.
# The DFS trees are the strongly connected components.



Revision as of 13:02, 10 October 2014

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 fro 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.