Tarjan’s Algorithm: Correctness and Linear-Time Bound

From Low-Link Values to Components

Tarjan’s algorithm finds all strongly connected components in one depth-first search. Its key decision is local: when a vertex finishes, compare its low-link value with its discovery index. Equality identifies a component to pop from a stack. The proof must account not only for vertices already popped and vertices not yet discovered, but also for older active vertices still on the stack. Those active vertices are essential: a route from the current vertex to one of them can show that the current vertex belongs to an earlier component.

Throughout, \(G=(V,E)\) is a finite directed simple graph. A directed path from \(u\) to \(v\) follows edges in their direction. Two vertices are strongly connected if each is reachable from the other; the strongly connected components are the maximal sets of pairwise strongly connected vertices. A DFS call from a vertex explores every outgoing edge of every vertex it discovers before returning. To handle a disconnected directed graph, start a DFS call at each vertex that has not yet been discovered.

Definition: Tarjan’s algorithm assigns each discovered vertex \(v\) a distinct discovery index \(\operatorname{index}(v)\), and maintains a stack of discovered vertices not yet assigned to a component. A vertex on this stack is active. Initially set \(\operatorname{low}(v)=\operatorname{index}(v)\). After a recursive DFS call from an undiscovered neighbor \(w\), update \(\operatorname{low}(v)\) to the minimum of its current value and \(\operatorname{low}(w)\). For an edge \(v\to w\) whose endpoint \(w\) is already on the stack, update \(\operatorname{low}(v)\) to the minimum of its current value and \(\operatorname{index}(w)\). Edges to vertices no longer on the stack do not change \(\operatorname{low}(v)\). When \(v\)'s call finishes, if \(\operatorname{low}(v)=\operatorname{index}(v)\), pop vertices through and including \(v\); these popped vertices are output as one component.

Low-link values are computed during the search, so a value can depend on descendants of \(v\) in the DFS tree. Along a tree edge, the child’s low-link value is passed back to its parent. Along an edge to an active vertex, the discovery index of that endpoint is considered. An edge to a vertex already assigned to a component is ignored because it cannot connect the current unfinished component back to that vertex.

Why a Root Vertex Reaches the Vertices It Pops

We first record what a low-link value witnesses. At the return from a DFS call at \(x\), a strict decrease below \(\operatorname{index}(x)\) is obtained by following tree edges down from \(x\), then an edge to an older active vertex. The claim follows directly from the updates: a child update extends the tree-edge portion of such a route, and an update from an edge to an active vertex supplies its final edge. Taking a minimum selects one of these witnesses. In particular, if \(\operatorname{low}(x)<\operatorname{index}(x)\), there is such a route from \(x\) to an active vertex \(q\) with \(\operatorname{index}(q)=\operatorname{low}(x)\). The endpoint \(q\) is still active at \(x\)'s return: it has smaller index than \(x\), so it was discovered earlier, and the stack cannot pop it while \(x\) remains above it.

Lemma. If the call at \(v\) returns with \(\operatorname{low}(v)=\operatorname{index}(v)\), every vertex popped in that operation can reach \(v\).

Proof. The popped vertices are \(v\) and the active vertices above it on the stack. Each other such vertex \(x\) was discovered during the DFS call at \(v\), so it is a descendant of \(v\) in the DFS tree. At the return from \(v\), every descendant \(x\) has \(\operatorname{low}(x)\geq\operatorname{index}(v)\): a smaller value would have been passed up through the tree edges to \(v\), contradicting \(\operatorname{low}(v)=\operatorname{index}(v)\). Also, \(x\) did not pop itself when its own call returned, since it remains on the stack. Its low-link value was therefore strictly less than its own index. The low-link witness gives a route from \(x\) to an active vertex \(q\) with \(\operatorname{index}(q)=\operatorname{low}(x)\). If \(q\neq v\), it is also above \(v\) on the stack, and its index is strictly smaller than \(x\)'s. Apply the same argument to \(q\). The indices strictly decrease at each step and are all at least \(\operatorname{index}(v)\), so the process must reach \(v\). Concatenating the witnessed routes proves that \(x\) reaches \(v\). The vertex \(v\) reaches itself by a path of length zero. \(\square\)

In the other direction, every popped vertex is a descendant of \(v\), and the tree path from \(v\) to that descendant is a directed path. Thus \(v\) reaches every vertex popped with it. Together with the lemma, this proves that the popped set is strongly connected.

Excluding Vertices Outside the Popped Set

Lemma: Suppose the call at \(v\) returns with \(\operatorname{low}(v)=\operatorname{index}(v)\). No older active vertex outside the popped set is reachable from \(v\).

Proof. Let \(y\) be an older active vertex outside the popped set, so \(\operatorname{index}(y)<\operatorname{index}(v)\), and suppose, for contradiction, that \(v\) can reach \(y\). Follow a directed route from \(v\) to \(y\), and consider its first edge that leaves the DFS subtree rooted at \(v\). If this edge led to an undiscovered vertex, that vertex would be explored during the call at \(v\), and would belong to its subtree, contrary to the choice of the edge. If it led to a vertex already assigned to a component, that vertex could not continue along the route to the still-active \(y\): its DFS exploration had already exhausted its reachable vertices, including any then-active vertex reachable from it. Hence the first edge leaving the subtree reaches an active vertex \(z\) discovered before \(v\). The edge is examined while its starting vertex is explored; the tree path from \(v\) to that starting vertex propagates its low-link contribution back to \(v\). Therefore \(\operatorname{low}(v)\leq\operatorname{index}(z)<\operatorname{index}(v)\), contradicting the root test. This argument also covers an older active vertex left on the stack by an earlier DFS branch: the first active vertex reached on leaving \(v\)'s subtree is enough to force a strict decrease, whether or not it is the final target \(y\). \(\square\)

This boundary argument is useful because a route from \(v\) to an older active vertex need not make the low-link value equal to the index of the final target. The first active vertex encountered outside \(v\)'s subtree may be a different, more recently discovered vertex. Its index is still strictly less than \(\operatorname{index}(v)\), which is all that the contradiction requires.

Theorem: Each time Tarjan’s algorithm applies the root test at \(v\), it pops exactly the strongly connected component containing \(v\). Over the complete search, every vertex is output exactly once.

Proof. Let \(S\) be the set popped at \(v\). The preceding lemma and the DFS tree paths show that \(v\) and every vertex in \(S\) reach each other. It remains to show that no vertex outside \(S\) is strongly connected to \(v\). If an outside vertex \(w\) is undiscovered when the call at \(v\) returns, then \(v\) cannot reach \(w\): DFS explores every vertex reachable from \(v\) before returning. If \(w\) was already popped, then \(w\) cannot reach \(v\). Indeed, its DFS exploration was completed before it was popped, and if it could reach the then-undiscovered \(v\), that exploration would have discovered \(v\); if \(v\) was already active, a route from \(w\) to \(v\) would have kept \(w\) on the stack rather than popping it as a completed component. The remaining possibility is that \(w\) is an older active vertex below \(v\) on the stack. The preceding lemma shows that \(v\) cannot reach such a vertex. These cases exclude every vertex outside \(S\) from being strongly connected to \(v\), so \(S\) is exactly its component. Each popped vertex is removed permanently and output once; because the DFS eventually discovers every vertex, all components are output. \(\square\)

Worked Traces

Worked Example: A Component with a Back Edge

Let \(V=\{a,b,c\}\) and \(E=\{a\to b,b\to c,c\to a\}\). Start DFS at \(a\), scanning the single outgoing edge at each vertex. Use discovery indices \(1,2,3\), in order.

After discovering \(a\), the stack is \([a]\) and \(\operatorname{low}(a)=1\). Discover \(b\): the stack is \([a,b]\), with \(\operatorname{low}(b)=2\). Discover \(c\): the stack is \([a,b,c]\), with \(\operatorname{low}(c)=3\). The edge \(c\to a\) reaches an active vertex, so \(\operatorname{low}(c)=\min(3,\operatorname{index}(a))=\min(3,1)=1\). Returning to \(b\) gives \(\operatorname{low}(b)=\min(2,1)=1\); returning to \(a\) gives \(\operatorname{low}(a)=\min(1,1)=1\). Since \(\operatorname{low}(a)=\operatorname{index}(a)=1\), pop \(c,b,a\).

Check: the output is \(\{a,b,c\}\). The listed edges give the directed cycle \(a\to b\to c\to a\), so each vertex reaches each other vertex by following the cycle. The output is indeed one strongly connected component.

Worked Example: An Older Active Vertex from an Earlier Branch

Let \(V=\{y,z,v\}\) and \(E=\{y\to z,z\to y,y\to v,v\to z\}\). Start at \(y\) and scan \(y\to z\) before \(y\to v\). The discovery indices are \(\operatorname{index}(y)=1\), \(\operatorname{index}(z)=2\), and \(\operatorname{index}(v)=3\).

The edge \(z\to y\) gives \(\operatorname{low}(z)=\min(2,1)=1\). Thus \(z\) returns without popping, and the stack is still \([y,z]\). Next DFS discovers \(v\), making the stack \([y,z,v]\). The edge \(v\to z\) reaches an active vertex, so \(\operatorname{low}(v)=\min(3,2)=2\). Since \(2<3\), \(v\) does not pass the root test. Returning to \(y\), its low-link value is \(1\), so the algorithm pops \(v,z,y\).

Check: the edges give \(y\to v\to z\to y\), a directed cycle through all three vertices. All three belong in the same component. This trace also shows why the older active vertex \(z\) matters: ignoring the edge \(v\to z\) would incorrectly make \(\operatorname{low}(v)=3\) and pop \(v\) separately.

Worked Example: Several Components in One Search

Let \(V=\{1,2,3,4,5\}\) and \(E=\{1\to2,2\to1,2\to3,4\to5\}\). Search from \(1\), then start a new DFS at the least-numbered undiscovered vertex. The first call discovers \(1\) with index \(1\), then \(2\) with index \(2\). The edge \(2\to1\) gives \(\operatorname{low}(2)=1\). Next \(2\to3\) discovers \(3\) with index \(3\). Vertex \(3\) has no outgoing edges, so \(\operatorname{low}(3)=3\), and it pops alone. Returning to \(2\) gives \(\operatorname{low}(2)=\min(2,1,3)=1\); returning to \(1\) gives \(\operatorname{low}(1)=1\), so \(2\) and \(1\) pop together.

Vertices \(4\) and \(5\) are still undiscovered. The new DFS discovers \(4\) with index \(4\), then \(5\) with index \(5\). Vertex \(5\) has no outgoing edges, so it pops alone; vertex \(4\) then has \(\operatorname{low}(4)=4\) and also pops alone. The output is \(\{3\},\{1,2\},\{5\},\{4\}\).

Check: vertices \(1\) and \(2\) reach each other, while \(2\to3\) has no return route from \(3\). The edge \(4\to5\) has no return route either, and there are no edges between these groups. The four reported sets are exactly the strongly connected components.

Why the Running Time Is Linear

Theorem: With adjacency lists, Tarjan’s algorithm runs in \(O(|V|+|E|)\) time and uses \(O(|V|)\) additional space, apart from the graph representation and output.

Proof. Each vertex is discovered once, assigned one index and low-link value, pushed once, and popped once. Each directed edge appears once in the adjacency list of its tail and is scanned once. During that scan, the algorithm performs a constant number of tests and, when needed, one minimum update. The total time for these operations is at most a constant times \(|V|+|E|\), so it is \(O(|V|+|E|)\). The index, low-link value, and stack-membership information use a constant amount of storage per vertex; the DFS recursion stack and Tarjan stack each contain at most \(|V|\) vertices. Thus the additional space is \(O(|V|)\). \(\square\)

The adjacency-list assumption matters to this count: scanning all outgoing neighbors takes time proportional to the number of edges actually present. With an adjacency matrix, finding all neighbors of a vertex may instead require scanning a full row, giving a different bound.

Common Pitfall

A tempting but incorrect argument is that every vertex left on the stack when \(v\) returns must belong to \(v\)'s component. The second example disproves that shortcut for a general return: when \(v\) returns, its low-link value is \(2\), while its index is \(3\), so it does not pop a component at all. The root test is what licenses a pop. Even when the test succeeds, the proof must exclude older active vertices below \(v\), not just vertices already popped or not yet discovered. The boundary argument does so: any route from \(v\)'s DFS subtree to an older active vertex forces a low-link value strictly below \(\operatorname{index}(v)\).

Check Your Understanding

Use the root-test proof and the low-link updates to answer these questions.

For an edge from \(x\) to an already discovered vertex \(w\), why does Tarjan’s algorithm use \(\operatorname{index}(w)\) only when \(w\) is still on the stack?
In the second worked example, compute \(\operatorname{low}(v)\) if the edge \(v\to z\) is mistakenly ignored. Why would that produce an incorrect component?
Explain why the first active vertex reached when a route leaves \(v\)'s DFS subtree is enough to contradict a successful root test.
Why does a vertex popped before \(v\)'s root test cannot be strongly connected to \(v\)? State which direction of reachability is ruled out.
For a graph with \(n\) vertices and \(m\) directed edges represented by adjacency lists, identify the operations charged to the \(n\) term and the \(m\) term in the running-time bound.