Kosaraju: Difference between revisions
| (6 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
[[Category:Graph Algorithms]] | |||
== General information == | == General information == | ||
| Line 15: | Line 17: | ||
== Correctness == | == Correctness == | ||
First note that the transposition of all arcs does not change the SCC of a graph, so step 4 | First note that the transposition of all arcs does not change the SCC of a graph, so we have to show that step 4 correctly computes the SCC of the transpose of <math>G</math>. | ||
[[File:CondensedGraphKosaraju.jpg|200px|thumb|right|Construction of the condensed graph (example)]] | |||
Consider the condensed graph <math>G'</math> whose nodes are these SCC, and there is an arc from an SCC <math>C_i</math> to an SCC <math>C_j</math> in <math>G'</math> if, and only if, there is at least one arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in <math>G</math>. | Consider the condensed graph <math>G'</math> whose nodes are these SCC, and there is an arc from an SCC <math>C_i</math> to an SCC <math>C_j</math> in <math>G'</math> if, and only if, there is at least one arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in <math>G</math> and their union would consequently form a single larger SCC contradicting the construction of the condensed graph. | ||
In step 1, each [[Depth-first search|DFS]] run either meets ''all'' nodes of an SCC of <math>G</math> or ''none'' of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous [[Depth-first search|DFS]] runs. | In step 1, each [[Depth-first search|DFS]] run either meets ''all'' nodes of an SCC of <math>G</math> or ''none'' of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous [[Depth-first search|DFS]] runs. | ||
Due to the parenthetical order of the [[Depth-first search|DFS]], if an SCC <math>C_i</math> is reachable from an SCC <math>C_j</math> in <math>G</math>, then there is at least one node of <math>C_j</math> which appears after all nodes of <math>C_i</math> in the output sequence of step 1 (because it is finished in [[Depth-first search|DFS]] after the nodes of <math>C_i</math>). Equivalently, there is at least one node of <math>C_j</math> which appears before all nodes of <math>C_i</math> in the reverse order of step 2 on which step 4 is based. | |||
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 of step 4. 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>C_k</math> be the SCC | Let <math>C_i</math> and <math>C_j (i \neq 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 of step 4. 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>C_k</math> be the SCC which the start node of that run in step 4 belongs to (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^t</math>; in other words, <math>C_k</math> is reachable from <math>C_i</math> in <math>G</math>. However, then at least one node of <math>C_i</math> had had a higher finishing time in step 1 than the nodes of <math>C_k</math>, so it had been chosen as a start node in step 4 before any node of <math>C_k</math> and the whole SCC <math>C_i</math> had been seen in the [[Depth-first search|DFS]] run from this node which contradicts the assumption that it is seen in a [[Depth-first search|DFS]] run from a node of <math>C_k</math>. | ||
== Complexity == | == Complexity == | ||
Latest revision as of 07:37, 2 November 2015
General information
Algorithmic problem: Strongly connected components
Type of algorithm: loop
Abstract View
- Apply a repeated depth-first search to [math]\displaystyle{ G }[/math], the output order is parenthetical.
- Invert the output order of the nodes.
- Let [math]\displaystyle{ G^t=(V,A^t) }[/math] be the transpose of [math]\displaystyle{ G=(V,A) }[/math].
- Apply a repeated depth-first search to [math]\displaystyle{ G^t }[/math] with a modification: The order in which the nodes are considered as potential start nodes is the inverted parenthetical order from step 2.
- The node sets from the individual 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 we have to show that step 4 correctly computes the SCC of the transpose of [math]\displaystyle{ G }[/math].
Consider the condensed graph [math]\displaystyle{ G' }[/math] whose nodes are these SCC, and there is an arc from an SCC [math]\displaystyle{ C_i }[/math] to an SCC [math]\displaystyle{ C_j }[/math] in [math]\displaystyle{ G' }[/math] if, and only if, there is at least one arc in [math]\displaystyle{ G }[/math] from some node in [math]\displaystyle{ C_i }[/math] to some node in [math]\displaystyle{ C_j }[/math]. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in [math]\displaystyle{ G }[/math] and their union would consequently form a single larger SCC contradicting the construction of the condensed graph.
In step 1, each DFS run either meets all nodes of an SCC of [math]\displaystyle{ G }[/math] or none of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous DFS runs.
Due to the parenthetical order of the DFS, if an SCC [math]\displaystyle{ C_i }[/math] is reachable from an SCC [math]\displaystyle{ C_j }[/math] in [math]\displaystyle{ G }[/math], then there is at least one node of [math]\displaystyle{ C_j }[/math] which appears after all nodes of [math]\displaystyle{ C_i }[/math] in the output sequence of step 1 (because it is finished in DFS after the nodes of [math]\displaystyle{ C_i }[/math]). Equivalently, there is at least one node of [math]\displaystyle{ C_j }[/math] which appears before all nodes of [math]\displaystyle{ C_i }[/math] in the reverse order of step 2 on which step 4 is based.
Let [math]\displaystyle{ C_i }[/math] and [math]\displaystyle{ C_j (i \neq 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 of step 4. 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{ C_k }[/math] be the SCC which the start node of that run in step 4 belongs to (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^t }[/math]; in other words, [math]\displaystyle{ C_k }[/math] is reachable from [math]\displaystyle{ C_i }[/math] in [math]\displaystyle{ G }[/math]. However, then at least one node of [math]\displaystyle{ C_i }[/math] had had a higher finishing time in step 1 than the nodes of [math]\displaystyle{ C_k }[/math], so it had been chosen as a start node in step 4 before any node of [math]\displaystyle{ C_k }[/math] and the whole SCC [math]\displaystyle{ C_i }[/math] had been seen in the DFS run from this node which contradicts the assumption that it is seen in a DFS run from a node of [math]\displaystyle{ C_k }[/math].
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(|V|+|A|) }[/math].
Proof: Follows immediately from the linear asymptotic complexity of repeated DFS.
Pseudocode
STRONGLY-CONNECTED-COMPONENTS(D)
1 call DFS(D) to compute finishing times f[v] for each vertex v ∈ V
2 compute DT (w.r.t. step 3)
3 call DFS(DT), but in the main loop of DFS, consider the vertices in order of decreasing f[v] as computed in step 1
4 output the vertices of each tree in the DFS forest of step 3 as a separate strongly connected component