Content deleted Content added
m Dating maintenance tags: {{Citation Needed}} |
|||
Line 30:
Each node <code>v</code> is assigned a unique integer <code>v.index</code>, which numbers the nodes consecutively in the order in which they are discovered. It also maintains a value <code>v.lowlink</code> that represents the smallest index of any node on the stack known to be reachable from <code>v</code> through <code>v</code>'s DFS subtree, including <code>v</code> itself. Therefore <code>v</code> must be left on the stack if <code>v.lowlink < v.index</code>, whereas v must be removed as the root of a strongly connected component if <code>v.lowlink == v.index</code>. The value <code>v.lowlink</code> is computed during the depth-first search from <code>v</code>, as this finds the nodes that are reachable from <code>v</code>.
== The algorithm in pseudocode ==
Line 61:
''// Successor w is in stack S and hence in the current SCC''
''// If ''w'' is not on stack, then (''v'', ''w'') is an edge pointing to an SCC already found and must be ignored
''//
''// It says w.index not w.lowlink; that is deliberate and from the original paper''
''v''.lowlink := min(''v''.lowlink, ''w''.index)
Line 75:
output the current strongly connected component
The <code>index</code> variable is the depth-first search node number counter. <code>S</code> is the node stack, which starts out empty and stores the history of nodes explored but not yet committed to a strongly connected component.
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 <code>strongconnect</code> performs a single depth-first search of the graph, finding all successors from the node <code>v</code>, and reporting all strongly connected components of that subgraph.
Line 81:
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.
== Complexity ==
|