Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 02:54, 24 February 2019

Revision as of 19:57, 25 February 2019

Line 1:

{{cleanup HTML|date=February 2019}}

{{Infobox algorithm

|class=

Line 22 ⟶ 21:

=== Stack invariant ===

Nodes are placed on a [[Stack (data structure)|stack]] in the order in which they are visited. When the depth-first search recursively visits a node <ttcode>v</ttcode> and its descendants, those nodes are not all necessarily popped from the stack when this recursive call returns. The crucial [[Invariant (computer science)|invariant property]] is that a node remains on the stack after it has been visited if and only if there exists a path in the input graph from it to some node earlier on the stack.

At the end of the call that visits <ttcode>v</ttcode> and its descendants, we know whether <ttcode>v</ttcode> itself has a path to any node earlier on the stack. If so, the call returns, leaving <ttcode>v</ttcode> on the stack to preserve the invariant. If not, then <ttcode>v</ttcode> must be the root of its strongly connected component, which consists of <ttcode>v</ttcode> together with any nodes later on the stack than <ttcode>v</ttcode> (such nodes all have paths back to <ttcode>v</ttcode> but not to any earlier node, because if they had paths to earlier nodes then <ttcode>v</ttcode> would also have paths to earlier nodes which is false). The connected component rooted at <ttcode>v</ttcode> is then popped from the stack and returned, again preserving the invariant.

=== Bookkeeping ===

Each node <ttcode>v</ttcode> is assigned a unique integer <ttcode>v.index</ttcode>, which numbers the nodes consecutively in the order in which they are discovered. It also maintains a value <ttcode>v.lowlink</ttcode> that represents the smallest index of any node known to be reachable from <ttcode>v</ttcode> through <ttcode>v</ttcode>'s DFS subtree, including <ttcode>v</ttcode> itself. Therefore <ttcode>v</ttcode> must be left on the stack if <ttcode>v.lowlink < v.index</ttcode>, whereas v must be removed as the root of a strongly connected component if <ttcode>v.lowlink == v.index</ttcode>. The value <ttcode>v.lowlink</ttcode> is computed during the depth-first search from <ttcode>v</ttcode>, as this finds the nodes that are reachable from <ttcode>v</ttcode>.

== The algorithm in pseudocode ==

Line 79 ⟶ 78:

'''end function'''

The <ttcode>index</ttcode> variable is the depth-first search node number counter. <ttcode>S</ttcode> is the node stack, which starts out empty and stores the history of nodes explored but not yet committed to a strongly connected component. Note that this is not the normal depth-first search stack, as nodes are not popped as the search returns up the tree; they are only popped when an entire strongly connected component has been found.

The outermost loop searches each node that has not yet been visited, ensuring that nodes which are not reachable from the first node are still eventually traversed. The function <ttcode>strongconnect</ttcode> performs a single depth-first search of the graph, finding all successors from the node <ttcode>v</ttcode>, and reporting all strongly connected components of that subgraph.

When each node finishes recursing, if its lowlink is still set to its index, then it is the root node of a strongly connected component, formed by all of the nodes above it on the stack. The algorithm pops the stack up to and including the current node, and presents all of these nodes as a strongly connected component.

Note that <ttcode>''v''.lowlink := min(''v''.lowlink, ''w''.index) </ttcode> is the correct way to update <code>''v.lowlink''</code> if <code>''w''</code> is on stack. Because <code>''w''</code> is on the stack already, <code>''(v, w)''</code> is a back-edge in the DFS tree and therefore <code>''w''</code> is not in the subtree of <code>''v''</code>. Because <code>''v.lowlink''</code> takes into account nodes reachable only through the nodes in the subtree of <code>''v''</code> we must stop at <code>''w''</code> and use <code>''w.index''</code> instead of <code>''w.lowlink''</code>.

== Complexity ==

''Time Complexity'': The Tarjan procedure is called once for each node; the forall statement considers each edge at most once. The algorithm's running time is therefore linear in the number of edges and nodes in G, i.e. <math>O(|V|+|E|)</math>.

In order to achieve this complexity, the test for whether <ttcode>w</ttcode> is on the stack should be done in constant time.

This may be done, for example, by storing a flag on each node that indicates whether it is on the stack, and performing this test by examining the flag.

''Space Complexity'': The Tarjan procedure requires two words of supplementary data per vertex for the <ttcode>index</ttcode> and <ttcode>lowlink</ttcode> fields, along with one bit for <ttcode>onStack</ttcode> and another for determining when <ttcode>index</ttcode> is undefined. In addition, one word is required on each stack frame to hold <ttcode>v</ttcode> and another for the current position in the edge list. Finally, the worst-case size of the stack <ttcode>S</ttcode> must be <math>|V|</math> (i.e. when the graph is one giant component). This gives a final analysis of <math>O(|V|\cdot(2+5w))</math> where <math>w</math> is the machine word size. The variation of Nuutila and Soisalon-Soininen reduced this to <math>O(|V|\cdot(1+4w))</math> and, subsequently, that of Pearce requires only <math>O(|V|\cdot(1+3w))</math>.<ref>{{cite web|last=Nuutila|first=Esko|title=On Finding the Strongly Connected Components in a Directed Graph|url=https://doi.org/10.1016/0020-0190(94)90047-7|journal=Information Processing Letters|pages=9-14|volume=49|number=1|accessdate=13 December 2017}}</ref><ref>{{cite web|last=Pearce|first=David|title=A Space Efficient Algorithm for Detecting Strongly Connected Components|url=https://doi.org/10.1016/j.ipl.2015.08.010|journal=Information Processing Letters|pages=47-52|number=1|volume=116|accessdate=13 December 2017}}</ref>

==Additional remarks==