Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 14:45, 18 August 2021

Revision as of 15:57, 16 December 2021

Line 27:

=== Bookkeeping ===

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 the 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>