Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 13:56, 1 June 2020

Revision as of 03:14, 11 November 2020

Line 11:

|complete=

}}

'''Tarjan's algorithm''' is an [[algorithm]] in [[graph theory]] for finding the [[strongly connected component]]s 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]]. Tarjan's algorithm is named for its inventor, [[Robert Tarjan]].<ref>{{citation|first=R. E.|last=Tarjan|authorlinkauthor-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}}</ref>

== Overview ==

Line 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 <code>v</code> 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. In other words, it means that in the DFS a node would be only removed from the stack after all its connected paths have been traversed. When the DFS will backtrack it would remove the nodes on a single path and return back to the root in order to start a new path.

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

Line 95:

==Additional remarks==

While there is nothing special about the order of the nodes within each strongly connected component, one useful property of the algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse [[Topological sorting|topological sort]] of the [[Directed acyclic graph|DAG]] formed by the strongly connected components.<ref>{{cite web|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|accessdateaccess-date=9 February 2011}}</ref>

[[Donald Knuth]] described Tarjan's algorithm as one of his favorite implementations in the book ''The Stanford GraphBase''.<ref>Knuth, ''The Stanford GraphBase'', pages 512–519.</ref>