Kosaraju: Difference between revisions
| Line 11: | Line 11: | ||
# 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 from step 2. | # 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 | # The node sets from the applications of [[Depth-first search|DFS]] inside step 4 are exactly the SCC of <math>G</math>. | ||
== Correctness == | |||
Let <math>C_1,\ldots,C_k</math> denote the SCC of <math>G</math>. Consider the condensed graph whose nodes are these SCC, and there is an arc from <math>C_i</math> to <math>C_j</math> if, and only if, there is an arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. Obviously, this condensed graph is acyclic because any two nodes of <math>G</math> in the SCC on such a cycle are mutually reachable from each other in <math>G</math>. | |||
In step 1, each application of [[Depth-first search|DFS]] either meets all nodes of an SCC of <math>G</math>or none of its nodes. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC in the condensed graph, except for the SCC met in previous applications of [[Depth-first search|DFS]]. | |||
== Correctness == | == Correctness == | ||
Revision as of 13:17, 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 node sets from the applications of DFS inside step 4 are exactly the SCC of [math]\displaystyle{ G }[/math].
Correctness
Let [math]\displaystyle{ C_1,\ldots,C_k }[/math] denote the SCC of [math]\displaystyle{ G }[/math]. Consider the condensed graph whose nodes are these SCC, and there is an arc from [math]\displaystyle{ C_i }[/math] to [math]\displaystyle{ C_j }[/math] if, and only if, there is an arc in [math]\displaystyle{ G }[/math] from some node in [math]\displaystyle{ C_i }[/math] to some node in [math]\displaystyle{ C_j }[/math]. Obviously, this condensed graph is acyclic because any two nodes of [math]\displaystyle{ G }[/math] in the SCC on such a cycle are mutually reachable from each other in [math]\displaystyle{ G }[/math].
In step 1, each application of DFS either meets all nodes of an SCC of [math]\displaystyle{ G }[/math]or none of its nodes. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC in the condensed graph, except for the SCC met in previous applications of DFS.
Correctness
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(|V|+|A|) }[/math].
Proof: Follows immediately from the linear asymptotic complexity of DFS.