Algorithm Deep Dive: Gabow's SCC Algorithm

History of DFS-Based SCC Algorithms

A strongly connected component (SCC) is a maximal group of directed-graph vertices in which every vertex can reach every other. Several classic linear-time algorithms discover the same partition, but they remember different evidence while depth-first search unfolds.

1972

Robert Tarjan published a one-pass DFS algorithm whose discovery numbers and low-link information identify SCC roots.

1981

Micha Sharir published a two-pass strong-connectivity algorithm and applied it to data-flow analysis. The method is now commonly called Kosaraju–Sharir.

2000

Harold N. Gabow published Path-based depth-first search for strong and biconnected components. The paper traces the path-based viewpoint to earlier proposals by Purdom and Munro and gives linear-time implementations using stacks and arrays.

Gabow's contribution is best understood as a different representation of the unresolved DFS structure. Tarjan stores a numerical summary—the earliest reachable discovery point. Gabow keeps the candidate boundaries themselves on a second stack. Both are one-pass, linear-time methods; which is clearer or faster depends on the implementation and platform.

Primary sources: Tarjan (1972), Sharir (1981), and Gabow (2000).

What an SCC Represents

Mutual reachability is an equivalence relation: it groups vertices into disjoint SCCs. If each SCC is collapsed into one super-vertex, the remaining condensation graph is always a directed acyclic graph (DAG). A directed cycle between two super-vertices would mean those groups were mutually reachable and should have been one SCC.

Inside each dashed region, every vertex can reach every other. Collapsing those regions leaves only one-way dependencies: A → B → C.

SCCs partition Veach SCC is maximalcondensation is a DAG

Working Principle: Two Stacks

Vertex stack S

Contains every discovered vertex that has not yet been assigned to a completed SCC. Its suffixes are the material from which components are emitted.

Boundary stack P

Contains candidate roots in increasing discovery order. These entries divide S into candidate component blocks.

Discover a vertex

Assign its preorder number and push it onto both S and P. Initially it may be the root of a new SCC.

Contract on an active edge

For an edge u → v where v is discovered but unassigned, pop P while preorder[P.top] > preorder[v]. Those later boundaries can no longer represent separate SCCs.

Emit at a surviving boundary

After all edges of u are processed, if u is still P's top, pop the suffix of S through u. That suffix is one complete SCC.

The active edge 2 → 0 closes a cycle. Stack P forgets the internal boundaries at 1 and 2; stack S keeps all three vertices until the entire SCC is safe to output.

The mental model

S asks, “Which vertices are still unresolved?” P asks, “Where could the unresolved components begin?” An active edge can invalidate several tentative beginnings at once.

The Three DFS Edge Cases

1. v is unvisited

Discover v, push it onto both stacks, and continue DFS from it. The current component boundary remains tentative.

2. v is active

Vertex v has a preorder number but no component ID. Contract P down toward v's preorder because the edge links current candidate blocks.

3. v is already assigned

Ignore the edge for stack contraction. A completed SCC will never merge with a still-active one during this DFS.

4. u finishes

This is not an edge case, but the decisive event: u emits an SCC exactly when it remains on top of P.

“Active” is not the same as “visited”

A visited vertex may already belong to a completed component. The implementation therefore checks component[v] == -1, not merely whether v has been visited.

Worked Example: Three Components

Use the graph from the first figure: cycle 0 → 1 → 2 → 0, bridge 2 → 3, cycle 3 ↔ 4, and edge 4 → 5. Assume adjacency lists are scanned in the order shown.

Event	S (bottom → top)	P (bottom → top)	Meaning
discover 0, 1, 2	`[0,1,2]`	`[0,1,2]`	Each vertex initially starts a candidate block.
edge 2 → 0	`[0,1,2]`	`[0]`	Pop boundaries 2 and 1; the cycle has one surviving root.
discover 3, 4	`[0,1,2,3,4]`	`[0,3,4]`	Two new candidate boundaries appear.
edge 4 → 3	`[0,1,2,3,4]`	`[0,3]`	Boundary 4 is internal to SCC {3,4}.
discover and finish 5	`[0,1,2,3,4]`	`[0,3]`	First output is {5}; it is a sink in the condensation DAG.
finish 3	`[0,1,2]`	`[0]`	Pop through 3 and output {4,3}.
finish 0	`[]`	`[]`	Pop through 0 and output {2,1,0}.

A component is emitted only after its DFS descendants are resolved, so Gabow naturally produces SCCs in reverse topological order of the condensation DAG.

Correctness Through Four Invariants

Unresolved-vertex invariant: S contains exactly the discovered vertices that have not yet been assigned to an SCC.
Ordered-boundary invariant: P is a subsequence of S whose preorder numbers strictly increase. Its entries partition S into consecutive candidate blocks.
Contraction invariant: an active edge to an earlier preorder proves that every later candidate boundary down to that point is internal, so popping those boundaries cannot separate a real SCC.
Emission invariant: if u remains at the top of P after all its outgoing edges are processed, the suffix of S beginning at u is mutually reachable and cannot reach an earlier active candidate. It is therefore maximal and safe to emit.

Every emitted group is strongly connected, no two emitted groups overlap, and every vertex is eventually emitted. Together these facts prove that the algorithm returns exactly the SCC partition.

Complexity Analysis

DFS examines every vertex and edge once. A vertex is pushed once and popped once from S, and it is pushed once and popped at most once from P. Although one edge may pop many boundaries, there are at most V boundary pops over the entire run—an amortized argument.

$$\text{Time: } O(V + E) \qquad \text{Auxiliary space: } O(V)$$

Algorithm	DFS passes	Main state	Reverse graph?	Complexity
Gabow	1	vertex stack S + boundary stack P	No	O(V + E)
Tarjan	1	one stack + low-link values	No	O(V + E)
Kosaraju–Sharir	2	finish order + second traversal	Yes	O(V + E)

The asymptotic guarantees are identical. Choose based on which invariant your team can implement, review, and maintain most confidently.

Implementation

def gabow_scc(adj):
    """Return (components, component_of) for a 0-indexed digraph."""
    n = len(adj)
    preorder = [-1] * n
    component_of = [-1] * n
    S, P, components = [], [], []
    clock = 0

    def discover(u):
        nonlocal clock
        preorder[u] = clock
        clock += 1
        S.append(u)
        P.append(u)

    for start in range(n):
        if preorder[start] != -1:
            continue

        discover(start)
        # Each frame stores [vertex, index of next outgoing edge].
        frames = [[start, 0]]

        while frames:
            u, edge_index = frames[-1]

            if edge_index < len(adj[u]):
                v = adj[u][edge_index]
                frames[-1][1] += 1
                if not 0 <= v < n:
                    raise ValueError(f"invalid neighbor {v} from vertex {u}")

                if preorder[v] == -1:
                    discover(v)
                    frames.append([v, 0])
                elif component_of[v] == -1:  # v is still active
                    while preorder[P[-1]] > preorder[v]:
                        P.pop()
            else:
                frames.pop()
                if P[-1] == u:
                    P.pop()
                    component_id = len(components)
                    component = []
                    while True:
                        v = S.pop()
                        component_of[v] = component_id
                        component.append(v)
                        if v == u:
                            break
                    components.append(component)

    return components, component_of


# SCCs are returned in reverse topological (sink-first) order.
graph = [[1], [2], [0, 3], [4], [3, 5], []]
components, component_of = gabow_scc(graph)
print("SCCs:", components)
print("Component IDs:", component_of)

#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;

class GabowSCC {
    struct Frame { int u; size_t nextEdge; };
    const vector<vector<int>>& adj;
    vector<int> preorder, componentOf, S, P;
    vector<vector<int>> components;
    int clock = 0;

    void discover(int u) {
        preorder[u] = clock++;
        S.push_back(u);
        P.push_back(u);
    }

public:
    explicit GabowSCC(const vector<vector<int>>& graph)
        : adj(graph), preorder(graph.size(), -1),
          componentOf(graph.size(), -1) {
        const int n = static_cast<int>(adj.size());

        for (int start = 0; start < n; ++start) {
            if (preorder[start] != -1) continue;
            discover(start);
            vector<Frame> frames = {{start, 0}};

            while (!frames.empty()) {
                Frame& frame = frames.back();
                int u = frame.u;

                if (frame.nextEdge < adj[u].size()) {
                    int v = adj[u][frame.nextEdge++];
                    if (v < 0 || v >= n)
                        throw out_of_range("neighbor outside vertex range");

                    if (preorder[v] == -1) {
                        discover(v);
                        frames.push_back({v, 0});
                    } else if (componentOf[v] == -1) {
                        while (preorder[P.back()] > preorder[v])
                            P.pop_back();
                    }
                } else {
                    frames.pop_back();
                    if (P.back() == u) {
                        P.pop_back();
                        int id = static_cast<int>(components.size());
                        vector<int> component;
                        while (true) {
                            int v = S.back(); S.pop_back();
                            componentOf[v] = id;
                            component.push_back(v);
                            if (v == u) break;
                        }
                        components.push_back(move(component));
                    }
                }
            }
        }
    }

    const vector<vector<int>>& getComponents() const { return components; }
    const vector<int>& getComponentIds() const { return componentOf; }
};

int main() {
    vector<vector<int>> graph = {{1}, {2}, {0, 3}, {4}, {3, 5}, {}};
    GabowSCC solver(graph);
    for (const auto& component : solver.getComponents()) {
        cout << "[ ";
        for (int v : component) cout << v << ' ';
        cout << "]\n";
    }
}

import java.util.*;

public class GabowSCC {
    private static final class Frame {
        int vertex, nextEdge;
        Frame(int vertex) { this.vertex = vertex; }
    }

    private final List<List<Integer>> graph;
    private final int[] preorder, componentOf;
    private final List<Integer> S = new ArrayList<>();
    private final List<Integer> P = new ArrayList<>();
    private final List<List<Integer>> components = new ArrayList<>();
    private int clock = 0;

    public GabowSCC(List<List<Integer>> graph) {
        this.graph = graph;
        preorder = new int[graph.size()];
        componentOf = new int[graph.size()];
        Arrays.fill(preorder, -1);
        Arrays.fill(componentOf, -1);
        run();
    }

    private void discover(int u) {
        preorder[u] = clock++;
        S.add(u);
        P.add(u);
    }

    private void run() {
        int n = graph.size();
        for (int start = 0; start < n; start++) {
            if (preorder[start] != -1) continue;
            discover(start);
            List<Frame> frames = new ArrayList<>();
            frames.add(new Frame(start));

            while (!frames.isEmpty()) {
                Frame frame = frames.get(frames.size() - 1);
                int u = frame.vertex;

                if (frame.nextEdge < graph.get(u).size()) {
                    int v = graph.get(u).get(frame.nextEdge++);
                    if (v < 0 || v >= n)
                        throw new IllegalArgumentException("invalid neighbor " + v);

                    if (preorder[v] == -1) {
                        discover(v);
                        frames.add(new Frame(v));
                    } else if (componentOf[v] == -1) {
                        while (preorder[P.get(P.size() - 1)] > preorder[v])
                            P.remove(P.size() - 1);
                    }
                } else {
                    frames.remove(frames.size() - 1);
                    if (P.get(P.size() - 1) == u) {
                        P.remove(P.size() - 1);
                        int id = components.size();
                        List<Integer> component = new ArrayList<>();
                        while (true) {
                            int v = S.remove(S.size() - 1);
                            componentOf[v] = id;
                            component.add(v);
                            if (v == u) break;
                        }
                        components.add(component);
                    }
                }
            }
        }
    }

    public List<List<Integer>> getComponents() { return components; }
    public int[] getComponentIds() { return componentOf.clone(); }

    public static void main(String[] args) {
        List<List<Integer>> graph = List.of(
            List.of(1), List.of(2), List.of(0, 3),
            List.of(4), List.of(3, 5), List.of()
        );
        GabowSCC solver = new GabowSCC(graph);
        System.out.println("SCCs: " + solver.getComponents());
        System.out.println("Component IDs: " + Arrays.toString(solver.getComponentIds()));
    }
}

Real-World Applications

2-SAT

Build an implication graph. A formula is unsatisfiable exactly when some variable x and its negation belong to the same SCC.

Compilers and data flow

Collapse mutually dependent blocks before solving data-flow equations over the resulting DAG.

Wait-for graphs

A nontrivial SCC exposes a circular waiting dependency and helps localize a possible deadlock.

Graph preprocessing

Compress cycles into super-vertices, then run scheduling, reachability, or dynamic programming on the condensation DAG.

SCCs are often the preprocessing step

The component partition explains the cyclic part of a directed graph; the condensation DAG exposes the one-way structure between those cycles.

Exercises

1. Trace a pure cycle

Run the algorithm on 0 → 1 → 2 → 3 → 0. Record S and P after every discovery, edge scan, and finish event. Which single edge removes the most entries from P?

2. Distinguish active from assigned

Add edge 1 → 5 to the worked graph. When that edge is eventually examined, explain why it cannot merge {0,1,2} with the already completed SCC {5}.

3. Compare representations

For the worked example, place Gabow's P stack beside Tarjan's low-link values. Identify the moment when each method discovers that vertices 3 and 4 share one SCC.

4. Prove the output order

Show that for every condensation edge A → B with A ≠ B, component B is emitted before component A. Then explain how to obtain topological order.

Limitations

Static snapshot: edge insertions or deletions can invalidate the partition; the basic algorithm must be rerun.
Order is structural, not sorted: vertices within an SCC follow stack-pop order, and SCCs are emitted sink-first. Sort only if an interface requires deterministic presentation.
Linear auxiliary memory: discovery numbers, component IDs, S, P, and explicit DFS frames all require O(V) space.
Directed connectivity only: use ordinary DFS or union–find for undirected connected components.

About recursion depth

Textbook versions usually express Gabow recursively and may overflow the call stack on a long directed path. The implementations above preserve the same enter/scan/finish events with explicit frame stacks, so their depth is limited by available heap memory instead.

Cookie Consent

Gabow's SCC Algorithm

Contents

History of DFS-Based SCC Algorithms

What an SCC Represents

Working Principle: Two Stacks

Vertex stack S

Boundary stack P

Discover a vertex

Contract on an active edge

Emit at a surviving boundary

The mental model

The Three DFS Edge Cases

1. v is unvisited

2. v is active

3. v is already assigned

4. u finishes

“Active” is not the same as “visited”

Worked Example: Three Components

Correctness Through Four Invariants

Complexity Analysis

Implementation

Real-World Applications

2-SAT

Compilers and data flow

Wait-for graphs

Graph preprocessing

SCCs are often the preprocessing step

Exercises

1. Trace a pure cycle

2. Distinguish active from assigned

3. Compare representations

4. Prove the output order

Limitations

About recursion depth

Cookie Consent

Gabow's SCC Algorithm

Contents

History of DFS-Based SCC Algorithms

What an SCC Represents

Working Principle: Two Stacks

Vertex stack S

Boundary stack P

Discover a vertex

Contract on an active edge

Emit at a surviving boundary

The mental model

The Three DFS Edge Cases

1. v is unvisited

2. v is active

3. v is already assigned

4. u finishes

“Active” is not the same as “visited”

Worked Example: Three Components

Correctness Through Four Invariants

Complexity Analysis

Implementation

Real-World Applications

2-SAT

Compilers and data flow

Wait-for graphs

Graph preprocessing

SCCs are often the preprocessing step

Exercises

1. Trace a pure cycle

2. Distinguish active from assigned

3. Compare representations

4. Prove the output order

Limitations

About recursion depth

Related Deep Dives

Graph Theory Series

Tarjan's SCC Algorithm

Kosaraju's SCC Algorithm