Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 18:06, 29 April 2021

Revision as of 18:01, 9 August 2021

Line 11:

|complete=

}}

'''Tarjan's strongly connected components algorithm''' is an [[algorithm]] in [[graph theory]] for finding the [[strongly connected component]]s (SCCs) of a [[directed graph]]. It runs in [[linear time]], matching the time bound for alternative methods including [[Kosaraju's algorithm]] and the [[path-based strong component algorithm]]. The algorithm is named for its inventor, [[Robert Tarjan]].<ref name=Tarjan>{{citation|first=R. E.|last=Tarjan|author-link=Robert Tarjan|title=Depth-first search and linear graph algorithms|journal=[[SIAM Journal on Computing]]|volume=1|year=1972|issue=2|pages=146–160|doi=10.1137/0201010|citeseerx=10.1.1.327.8418}}</ref>

== Overview ==

Line 28:

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

== The algorithm in pseudocode ==