Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 20:54, 1 August 2025

Latest revision as of 20:48, 26 August 2025

(One intermediate revision by the same user not shown)

Line 17:

== Overview ==

The algorithm takes a [[directed graph]] as input, and produces a [[Partition of a set|partition]] of the graph's [[Vertex (graph theory)|vertices]] into the graph's strongly connected components. Each vertex of the graph appears in exactly one of the strongly connected components. Any vertex that is not on a directed cycle forms a strongly connected component all by itself: for example, aany vertex whose in-degree or out-degree is 0, or anyevery vertex of ana [[directed acyclic graph]].

The basic idea of the algorithm is this: a depth-first search (DFS) begins from an arbitrary start node (and subsequent depth-first searches are conducted on any nodes that have not yet been found). As usual with depth-first search, the search visits every node of the graph exactly once, refusing to revisit any node that has already been visited. Thus, the collection of search trees is a [[Spanning forest#Spanning forests|spanning forest]] of the graph. The strongly connected components will be recovered as certain subtrees of this forest. The roots of these subtrees are called the "roots" of the strongly connected components. Any node of a strongly connected component might serve as a root, if it happens to be the first node of a component that is discovered by search.

Line 23:

=== 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 beis only removed from the DFS stack afterwhen all of its connected paths have been traversed. When the DFS will backtrack it would remove the nodes on a single path and return 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.

=== Bookkeeping ===