Tarjan's strongly connected components algorithm: Difference between revisions

Content deleted Content added
AnomieBOT (talk | contribs)
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>.
 
Note that theThe lowlink is different from the lowpoint, which is the smallest index reachable from <code>v</code> through any part of the graph.<ref name=Tarjan/>{{rp|156}}<ref>{{cite web |title=Lecture #19: Depth First Search and Strong Components |url=https://www.cs.cmu.edu/~15451-f18/lectures/lec19-DFS-strong-components.pdf |website=15-451/651: Algorithms Fall 2018 |publisher=Carnegie Mellon University |access-date=9 August 2021 |pages=7-8}}</ref>
 
== 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
''// Note: The next line may look odd - but is correct.''
''// 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. Note that thisThis 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 <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.
 
Note that <code>''v''.lowlink := min(''v''.lowlink, ''w''.index)</code> 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>{{Citation Needed|date=October 2023}}.
 
== Complexity ==