Discovery Order, Low Values, and the Active Stack
Tarjan’s strongly connected components algorithm uses one depth-first search (DFS) to organize its work. Its bookkeeping depends on two different questions: when was a vertex first discovered, and how far back in discovery order can the current vertex’s DFS descendants reach while the relevant vertices are still active? The first question gives a discovery index; the second is recorded by a low-link value. A stack keeps track of discovered vertices that have not yet been placed in an output block.
Throughout, \(G=(V,E)\) is a finite simple directed graph. A directed path from \(u\) to \(v\) follows the direction of every edge. Two vertices are strongly connected if each can reach the other by a directed path; a strongly connected component is a maximal set of pairwise strongly connected vertices. Tarjan’s algorithm runs DFS from each vertex not yet discovered, using a fixed order for each adjacency list. The mechanics and invariants below concern the labels and stack; the full proof that the output blocks are exactly the strongly connected components is a separate result.
How Low-Link Values Are Updated
While scanning the outgoing edges of a discovered vertex \(v\), use the following rules. If \(v\to w\) leads to an undiscovered vertex, it is a DFS tree edge: recursively search from \(w\), then update \(\operatorname{low}[v]\) using \(\operatorname{low}[w]\). If \(w\) has already been discovered and is still on the stack, update using \(\operatorname{index}[w]\). If \(w\) has already been removed from the stack, do not update \(\operatorname{low}[v]\) from this edge.
The second rule is often described as the update for a back edge, but that name needs care in a directed DFS. An edge from \(v\) to an ancestor is a back edge, and its target is on the stack. However, an edge to a previously explored vertex can also have a target still on the stack, even if that target is not an ancestor in the current recursive call chain. The algorithm uses the on-stack test, not the edge’s name, to decide whether to update. An edge to a vertex already removed from the stack is ignored even though that vertex has been visited.
The tree-edge rule uses the child’s low value; the on-stack-edge rule uses the target’s discovery index. These are not interchangeable. A child’s low value summarizes what was found during its recursive search, whereas an edge being scanned now gives a direct link to its target \(w\). Using \(\operatorname{low}[w]\) for that direct edge could import information that is not justified by this edge.
The Stack Invariant
The stack is not simply the current DFS recursion path. A recursive call can finish while its vertex remains on the stack, waiting for a later call to determine whether it belongs in the same output block. The stack may therefore contain vertices from several finished recursive calls, as well as vertices in calls that are still active.
Proof. Initially no vertex has been discovered and the stack is empty, so both claims hold. When an undiscovered vertex is first visited, it receives a new index, larger than every index assigned so far, and is pushed at the top. Thus it joins the set of discovered vertices not yet removed, and the increasing order is preserved. Scanning an edge or returning from a recursive call does not by itself change stack membership. When the algorithm removes a block, it pops vertices from the top through the designated vertex. Those vertices form a suffix, are removed from the stack, and are precisely the vertices newly placed in that output block. No other vertices change status. These are all operations that affect the stack, so the invariant holds throughout the search. \(\square\)
This invariant explains why “visited” and “active” are not synonyms. A vertex that has been discovered but has already been popped is visited, yet it is no longer on the stack. Only the latter status triggers the on-stack update rule. It also explains why a finished recursive call can still matter: its vertex may remain in the stack and can be the target of an edge scanned later.
Tracing the Updates
Worked Example: A Tree Edge and a Back Edge
Let \(G=(V,E)\) be the directed graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd,ca\}\). Search from \(a\), scanning outgoing edges in the order shown by \(E\). The DFS tree edges are \(ab,bc,cd\); the remaining edge \(ca\) goes from \(c\) to the ancestor \(a\).
| Event | Indices and low values after event | Stack, bottom to top |
|---|---|---|
| Discover \(a\) | \(\operatorname{index}[a]=0,\ \operatorname{low}[a]=0\) | \([a]\) |
| Discover \(b\) by \(ab\) | \(\operatorname{index}[b]=1,\ \operatorname{low}[b]=1\) | \([a,b]\) |
| Discover \(c\) by \(bc\) | \(\operatorname{index}[c]=2,\ \operatorname{low}[c]=2\) | \([a,b,c]\) |
| Discover \(d\) by \(cd\); \(d\) has no outgoing edges | \(\operatorname{index}[d]=3,\ \operatorname{low}[d]=3\) | \([a,b,c,d]\) |
| Finish \(d\); pop its block | \(\operatorname{low}[d]=3\) | \([a,b,c]\) |
| Scan \(ca\), with \(a\) still on the stack | \(\operatorname{low}[c]=\min(2,0)=0\) | \([a,b,c]\) |
| Return from \(c\) to \(b\) | \(\operatorname{low}[b]=\min(1,0)=0\) | \([a,b,c]\) |
| Return from \(b\) to \(a\) | \(\operatorname{low}[a]=\min(0,0)=0\) | \([a,b,c]\) |
The edge \(cd\) is a tree edge, so when \(d\)'s search returns, the comparison is with \(\operatorname{low}[d]=3\). The edge \(ca\) is to an already discovered vertex still on the stack, so the comparison is with \(\operatorname{index}[a]=0\). The updated value at \(c\) then propagates to \(b\) and \(a\) by the tree-edge rule.
Check: The displayed low values are \(0,0,0,3\) for \(a,b,c,d\), respectively. The edge \(ca\) closes the directed cycle \(a\to b\to c\to a\), while \(d\) has no path back to \(c\); the computed labels distinguish the cycle’s vertices from \(d\) in this trace. The popped vertex \(d\) is no longer on the stack when the search returns to \(c\).
Worked Example: A Previously Finished Call Still on the Stack
Let \(V=\{a,b,c\}\) and \(E=\{ab,ba,ac,cb\}\), with \(a\)'s outgoing edges scanned in order \(ab,ac\). Start DFS at \(a\). The point of the trace is that the recursive call at \(b\) can finish without removing \(b\) from the stack.
| Event | Indices and low values after event | Stack, bottom to top |
|---|---|---|
| Discover \(a\) | \(\operatorname{index}[a]=0,\ \operatorname{low}[a]=0\) | \([a]\) |
| Discover \(b\) by \(ab\); scan \(ba\) | \(\operatorname{index}[b]=1,\ \operatorname{low}[b]=\min(1,0)=0\) | \([a,b]\) |
| Return from \(b\) to \(a\) | \(\operatorname{low}[a]=\min(0,0)=0\) | \([a,b]\) |
| Discover \(c\) by \(ac\); scan \(cb\) | \(\operatorname{index}[c]=2,\ \operatorname{low}[c]=\min(2,1)=1\) | \([a,b,c]\) |
| Return from \(c\) to \(a\) | \(\operatorname{low}[a]=\min(0,1)=0\) | \([a,b,c]\) |
| Finish \(a\); pop through \(a\) | All three vertices are removed in this block | \([]\) |
When \(c\to b\) is scanned, the recursive call at \(b\) has already returned, but \(b\) remains on the stack. It is not an ancestor on the current call chain \(a,c\); nevertheless, the on-stack rule applies and uses \(\operatorname{index}[b]=1\). This illustrates why checking only whether a target is a current recursive ancestor would be incorrect.
Check: The updates give \(\operatorname{low}[a]=0\), \(\operatorname{low}[b]=0\), and \(\operatorname{low}[c]=1\). The directed cycle \(a\to c\to b\to a\) verifies directly that all three vertices can reach one another.
Worked Example: An Edge to a Popped Vertex Is Ignored
Let \(V=\{a,b,c\}\) and \(E=\{ab,ac,cb\}\), with \(a\)'s outgoing edges scanned in order \(ab,ac\). Begin at \(a\).
| Event | Indices and low values after event | Stack, bottom to top |
|---|---|---|
| Discover \(a\) | \(\operatorname{index}[a]=0,\ \operatorname{low}[a]=0\) | \([a]\) |
| Discover \(b\); \(b\) has no outgoing edges | \(\operatorname{index}[b]=1,\ \operatorname{low}[b]=1\) | \([a,b]\) |
| Finish \(b\); pop \(b\) | \(\operatorname{low}[b]=1\) | \([a]\) |
| Return to \(a\) and update from tree child \(b\) | \(\operatorname{low}[a]=\min(0,1)=0\) | \([a]\) |
| Discover \(c\); scan \(cb\), whose target is off the stack | \(\operatorname{index}[c]=2,\ \operatorname{low}[c]=2\) | \([a,c]\) |
| Finish \(c\); pop \(c\), then finish and pop \(a\) | \(\operatorname{low}[a]=0,\ \operatorname{low}[c]=2\) | \([]\) |
At \(cb\), \(b\) has already been discovered but is no longer on the stack. Therefore \(cb\) does not change \(\operatorname{low}[c]\). The tree-edge return from \(b\) to \(a\) still uses \(\operatorname{low}[b]\), as shown separately in the trace.
Check: The values are \(\operatorname{low}[a]=0\), \(\operatorname{low}[b]=1\), and \(\operatorname{low}[c]=2\). There is no directed path from \(b\) back to \(a\), nor from \(c\) back to either \(a\) or \(b\); thus the three vertices are separate strongly connected components, consistent with the three one-vertex blocks popped in the trace.
Reading the Bookkeeping Correctly
A useful way to remember the updates is to ask what information each edge supplies. A tree edge delegates the search to a child, whose recursive work is summarized by its low value. An edge to a vertex still on the stack supplies that target’s discovery index. An edge to a vertex off the stack supplies no update, because the target has already been removed from the active search bookkeeping.
Common mistake: treating every visited target as active. In the third example, a mistaken rule might use \(b\)'s index on edge \(cb\), even though \(b\) has been popped. That calculation would give \(\operatorname{low}[c]=\min(2,1)=1\). The correct calculation is \(\operatorname{low}[c]=2\), because \(b\) is off the stack and the edge is ignored. “Discovered” records that DFS has visited a vertex; “on the stack” records that it has not yet been removed in an output block. The two tests must not be conflated.
Likewise, do not update from a tree child before its recursive search returns: its final low value may depend on edges encountered deeper in that search. And do not replace \(\operatorname{index}[w]\) by \(\operatorname{low}[w]\) for a direct edge to an on-stack vertex. Each rule has a distinct role in maintaining the labels. The subsequent correctness analysis uses these mechanics to show why the blocks popped by the algorithm are the strongly connected components.
Check Your Understanding
For each question, distinguish discovery status from stack status and show the update that justifies your answer.
- In a directed DFS, \(v\to w\) is a tree edge and the recursive call at \(w\) returns with \(\operatorname{low}[w]=4\). If \(\operatorname{low}[v]=2\), what value does the tree-edge update give \(v\)?
- Suppose \(\operatorname{index}[v]=7\), \(\operatorname{low}[v]=7\), and \(v\to w\) where \(\operatorname{index}[w]=3\) and \(w\) is on the stack. Compute the updated low value.
- Why can a vertex whose recursive call has returned still be a valid target for the on-stack update?
- In the third worked example, what incorrect value results from applying the on-stack rule to \(cb\), and why is that rule inapplicable?
- State the two ordering and membership claims in the stack invariant. Which operation preserves the order of indices from bottom to top?