Kosaraju: Difference between revisions
| Line 14: | Line 14: | ||
== Correctness == | == Correctness == | ||
First note that the transposition of all arcs does not change the SCC of a graph, so step 2 indeed processes the SCC of <math>G</math>. | |||
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>. | 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 | In step 1, each [[Depth-first search|DFS]] run 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]] | ||
It is easy to see that all nodes of an SCC are finished consecutively; that is, all nodes of an SCC form a connected subsequence in the output sequence of step 1. In particular, it does not matter in step 4, which node of an SCC is chosen as a start node for a [[Depth-first searchDFS]] run. If an SCC <math>C_i</math> is reachable from an SCC <math>C_j</math>, then the nodes of <math>C_i</math> appear before the nodes of <math>C_j</math> in that order. I>n particular, the nodes of <math>C_i</math> appear '''after''' the nodes of <math>C_j</math> in the reverse order. | |||
Let <math>C_i</math> and <math>C_j</math> be two SCC of <math>G</math>. Since each SCC is processed exhaustively or not at all in a [[Depth-first search|DFS]] run, it suffices to show that <math>C_i</math> and <math>C_j</math> are not processed within the same run. Suppose for a contradiction that <math>C_i</math> and <math>C_j</math> are processed in the same [[Depth-first search|DFS]] run in step 4 (not necessarily in the same run in step 1). Let <math>CK</math> be the SCC to which the start node of that run belongs (possibly <math>k=i</math> or <math>k=j</math>). Without loss of generality, suppose <math>k\neq i</math>. Then <math>C_i</math> is reachable from <math>C_k</math> in <math>G'</math>; in other words, <math>C_k</math> is reachable from <math>C_i</math> in <math>G</math>. However, then the nodes of <math>C_i</math> have higher finishing times than the nodes of <math>C_k</math>, so some node of <math>C_i</math> had been chosen as a start node before any node of <math>C_k</math>. | |||
== Correctness == | == Correctness == | ||
Revision as of 08:39, 11 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
First note that the transposition of all arcs does not change the SCC of a graph, so step 2 indeed processes the SCC of [math]\displaystyle{ G }[/math].
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 DFS run 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
It is easy to see that all nodes of an SCC are finished consecutively; that is, all nodes of an SCC form a connected subsequence in the output sequence of step 1. In particular, it does not matter in step 4, which node of an SCC is chosen as a start node for a Depth-first searchDFS run. If an SCC [math]\displaystyle{ C_i }[/math] is reachable from an SCC [math]\displaystyle{ C_j }[/math], then the nodes of [math]\displaystyle{ C_i }[/math] appear before the nodes of [math]\displaystyle{ C_j }[/math] in that order. I>n particular, the nodes of [math]\displaystyle{ C_i }[/math] appear after the nodes of [math]\displaystyle{ C_j }[/math] in the reverse order.
Let [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math] be two SCC of [math]\displaystyle{ G }[/math]. Since each SCC is processed exhaustively or not at all in a DFS run, it suffices to show that [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math] are not processed within the same run. Suppose for a contradiction that [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j }[/math] are processed in the same DFS run in step 4 (not necessarily in the same run in step 1). Let [math]\displaystyle{ CK }[/math] be the SCC to which the start node of that run belongs (possibly [math]\displaystyle{ k=i }[/math] or [math]\displaystyle{ k=j }[/math]). Without loss of generality, suppose [math]\displaystyle{ k\neq i }[/math]. Then [math]\displaystyle{ C_i }[/math] is reachable from [math]\displaystyle{ C_k }[/math] in [math]\displaystyle{ G' }[/math]; in other words, [math]\displaystyle{ C_k }[/math] is reachable from [math]\displaystyle{ C_i }[/math] in [math]\displaystyle{ G }[/math]. However, then the nodes of [math]\displaystyle{ C_i }[/math] have higher finishing times than the nodes of [math]\displaystyle{ C_k }[/math], so some node of [math]\displaystyle{ C_i }[/math] had been chosen as a start node before any node of [math]\displaystyle{ C_k }[/math].
Correctness
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(|V|+|A|) }[/math].
Proof: Follows immediately from the linear asymptotic complexity of DFS.