How to Learn Gabow’s Path-Based SCC Algorithm: DFS Preorders, Two Stacks, Component Roots and Linear-Time Strong Connectivity

Can one depth-first search discover every strongly connected component without building a transpose graph and without storing Tarjan-style low-link values? Yes. Gabow’s path-based algorithm does it with two stacks and one beautifully compact invariant.

This Learning Hall article develops Gabow’s SCC algorithm from first principles. We begin with reachability and DFS, then build the two stacks, trace a complete example, derive the O(V+E) bound, compare the method with Kosaraju and Tarjan, and finish with iterative implementations, failure modes and professional testing.

Quick Read

A strongly connected component is a maximal set of vertices that can all reach one another.
Gabow performs one DFS over the original directed graph.
Stack S stores discovered vertices not yet assigned to a finished SCC.
Stack P stores candidate roots of SCCs.
When an edge reaches an active earlier vertex, candidate roots newer than that vertex are popped from P.
When the current DFS vertex is still the top of P after all outgoing edges are processed, it is the root of one complete SCC.
Vertices are popped from S through that root and assigned together.
Each vertex enters and leaves each stack at most once, so the total time is O(V+E).
The algorithm needs no transpose graph and no low-link array.

1. Beginner Level: What Is Strong Connectivity?

In a directed graph, being connected is not symmetric. If A can reach B, B may not be able to return to A. A strongly connected component, or SCC, is a maximal region in which every vertex can reach every other vertex.

A → B → C
↑       ↓
└───────┘

A, B and C form one SCC.

If we contract each SCC into one super-vertex, the resulting condensation graph is a DAG. That fact makes SCC decomposition useful in compilers, dependency analysis, model checking, graph databases and program analysis.

For the wider family first, see How to Learn Strongly Connected Components. This article owns the narrower Gabow path-based method.

2. DFS Gives Us an Order

Assign every vertex a preorder number when DFS first discovers it:

pre[v] = 0, 1, 2, 3, ...

Smaller preorder means “discovered earlier.” Edges from a current DFS region back to an active earlier vertex tell us that several candidate roots may really belong to one larger strongly connected component.

3. Stack S: Active Unassigned Vertices

The first stack, S, contains vertices that have been discovered but not yet assigned to a completed SCC. Think of S as the pool of vertices whose final component boundary is still open.

Once a component root is certified, all vertices belonging to that SCC are popped from S together.

4. Stack P: Candidate Component Roots

The second stack, P, stores candidate roots. Every newly discovered vertex begins as a possible SCC root, so it is pushed onto both stacks.

discover v:
    pre[v] = next_number
    S.push(v)
    P.push(v)

As DFS finds edges to earlier active vertices, some later root candidates become impossible and are removed from P.

5. The Key Update Rule

Suppose DFS at v sees an edge v→w. There are three useful cases.

w is unseen: recursively explore w.
w is already assigned to a finished SCC: ignore it for the current component boundary.
w is discovered but still active: pop from P while the top candidate was discovered later than w.

while pre[P.top()] > pre[w]:
    P.pop()

That loop is the heart of the path-based method. The edge reaches back far enough to show that those newer root candidates cannot close before the earlier active region containing w.

6. Detecting a Completed SCC

After all outgoing edges of v have been processed, check whether v is still the top of P. If it is, no active edge discovered during this DFS subtree forced the candidate root above v to collapse further upward. Therefore v closes one SCC.

if P.top() == v:
    P.pop()
    repeat:
        x = S.pop()
        assign x to current component
    until x == v

7. Complete Pseudocode

GABOW_SCC(G):
    index = 0
    component_id = 0
    S = empty stack
    P = empty stack

    for each vertex v:
        pre[v] = UNSEEN
        comp[v] = UNASSIGNED

    for each vertex v:
        if pre[v] == UNSEEN:
            DFS(v)

DFS(v):
    pre[v] = index
    index += 1
    S.push(v)
    P.push(v)

    for each w in G[v]:
        if pre[w] == UNSEEN:
            DFS(w)
        else if comp[w] == UNASSIGNED:
            while pre[P.top()] > pre[w]:
                P.pop()

    if P.top() == v:
        P.pop()
        repeat:
            w = S.pop()
            comp[w] = component_id
        until w == v
        component_id += 1

8. Trace a Small Example

Take edges A→B, B→C, C→A, C→D, D→E and E→D. DFS discovers A,B,C,D,E in that order. S and P initially grow together. The edge C→A pops B and C from P, leaving A as candidate root for the first cycle. Later E→D collapses E’s root candidate into D. D then closes {D,E}; those vertices are removed from S and marked assigned. Returning to C and then A eventually allows A to close {A,B,C}.

The important detail is that the already completed {D,E} component no longer participates when A’s component is decided.

9. Why the Algorithm Is Linear

DFS examines every vertex and edge once in the ordinary adjacency-list sense. Each vertex is pushed once onto S and once onto P. A vertex can be popped from each stack only once. Even though the while-loop may pop many items during one edge, those items never return.

DFS work:          O(V + E)
all S operations:  O(V)
all P operations:  O(V)
--------------------------------
total:             O(V + E)

10. Gabow vs Tarjan vs Kosaraju

Kosaraju: conceptually simple, but uses two DFS passes and normally the transpose graph.
Tarjan: one pass, one active stack and low-link values.
Gabow path-based: one pass, two stacks and no low-link field.

All three are O(V+E). The professional choice is therefore usually about implementation clarity, memory layout, recursion constraints, existing libraries and team familiarity rather than asymptotic complexity.

11. Why Two Stacks Can Be Easier to Reason About

Tarjan compresses “how far upward can this DFS subtree connect?” into a low-link number. Gabow keeps more of that boundary logic explicitly in P. For some learners, this turns a numerical invariant into a physical one: candidate roots literally disappear from the stack when an active edge proves they cannot be separate.

12. Iterative Engineering

Recursive DFS is elegant, but production graphs may have millions of vertices or adversarial depth. Replace the language call stack with an explicit frame stack containing the vertex, the next adjacency index and whether post-visit processing is pending.

Do not merely replace recursive calls with pushes. Gabow’s component-closing test must happen after all outgoing edges are processed, so an iterative version needs an explicit “return from child / finish vertex” state.

13. Failure Modes

Treating every previously seen vertex as active. Edges into already completed SCCs must not collapse P.
Comparing vertex IDs instead of preorder numbers. The stack rule is about DFS discovery order.
Closing a component before all outgoing edges are processed. The root test belongs to DFS postorder.
Forgetting disconnected starts. Run DFS from every unseen vertex.
Using recursion on unbounded-depth input. Convert to an explicit frame stack when necessary.
Emitting vertices but not stable component IDs. Decide whether downstream code needs sets, labels or a condensation DAG.

14. Testing Strategy

Single vertex with no edges.
Self-loop.
One directed cycle.
DAG, where every vertex should be its own SCC.
Two cycles connected in one direction.
Parallel edges and duplicate adjacency entries.
Large chain to test recursion depth.
Random graphs compared with Tarjan or NetworkX SCC output.
After decomposition, verify that the condensation graph is acyclic.

15. How to Learn It Efficiently

Use a trace table with columns for current DFS vertex, preorder, S, P, edge being examined and completed component. Start with a fully worked trace. Then fade one column at a time until the learner can reconstruct both stacks independently. This follows programming-education evidence that worked examples, code tracing and gradual removal of guidance are especially useful before independent code generation.

A strong PRIMM sequence is: predict the SCCs, run the supplied implementation, investigate each pop from P, modify one edge and predict the changed components, then make an iterative version.

16. Professional Applications

Collapse mutual dependencies before scheduling.
Find cycles in module and package graphs.
Reduce state-transition systems in model checking.
Find recursive regions in call graphs.
Build condensation DAGs for later dynamic programming.
Detect mutually reachable regions in large directed networks.

17. Practice Problems

Trace S and P on a four-cycle with one outgoing tail.
Add a back edge from the tail into the cycle and explain which P entries disappear.
Rewrite the recursive pseudocode using explicit DFS frames.
Instrument total P pops on a random graph and confirm the count never exceeds V.
Build a condensation DAG from Gabow’s component labels.
Compare output order with Tarjan and explain why component numbering may differ even when the partition is identical.

18. Sources and Further Reading

Final idea: Gabow’s algorithm is a lesson in making an invariant visible. S remembers everything still waiting for a component assignment. P remembers only the roots that are still plausible. Every important edge either extends the search or proves that some proposed boundary was too low. Once that picture is clear, the two-stack algorithm becomes far easier to remember—and much easier to verify.

Small Group Tutorials