Gabow's SCC Algorithm

A Bit of History

In 1980, Harold N. Gabow published "Path-based depth-first search for strong components" in the Journal on Computing. While Tarjan's 1972 algorithm pioneered single-pass $O(V+E)$ SCC identification using lowlink integers, and Kosaraju's 1978 algorithm required two full DFS passes and a transposed graph, Gabow realized that strongly connected components could be identified purely through stack manipulation. By maintaining a vertex stack and a boundary stack, Gabow eliminated integer min() updates on low-link arrays entirely, producing a clean, path-based algorithm.

Working Principle: Two Stacks

Gabow's algorithm performs a single DFS while maintaining two stacks:

1. Vertex Stack ($S$): Holds all vertices currently being explored that have not yet been assigned to a completed SCC.
2. Boundary Stack ($P$): Holds the "root" vertices of candidate SCCs currently on the DFS search path.

When traversing from node $u$ to neighbor $v$:

• If $v$ is unvisited: push $v$ onto $S$ and $P$, then recurse on $v$.
• If $v$ is already visited and still on stack $S$ (a back edge or cross edge to an active component): pop from $P$ all vertices whose discovery order is greater than $v$'s discovery order. This collapses the detected cycle into a single component boundary!
• When the DFS call for node $u$ completes: if $u$ is at the top of stack $P$, then $u$ is the root of an SCC. Pop $u$ from $P$, and pop all vertices from $S$ down through $u$ — they form a complete SCC!

Worked Example

Consider a directed graph with cycle $1 \to 2 \to 3 \to 1$ and edge $3 \to 4$:

• DFS visits 1, 2, 3: $S = [1, 2, 3]$, $P = [1, 2, 3]$.
• Edge $3 \to 1$: 1 is on stack $S$. Pop from $P$ until top is 1 $\implies$ $P = [1]$. The cycle $\{1, 2, 3\}$ is merged under root 1.
• DFS visits 4: $S = [1, 2, 3, 4]$, $P = [1, 4]$.
• DFS for 4 finishes: top of $P$ is 4. Pop 4 from $P$ and $S$. SCC 1: $\{4\}$.
• DFS for 1 finishes: top of $P$ is 1. Pop from $S$ down to 1. SCC 2: $\{3, 2, 1\}$.

Correctness & Invariants

The algorithm maintains the invariant that stack $P$ contains the entry points of all maximal strongly connected subgraphs in the current DFS tree. Whenever a cycle is completed by an edge back to an ancestor $v$, popping $P$ down to $v$ maintains the exact boundaries of active SCCs. Because every vertex is pushed and popped from $S$ and $P$ at most once, correctness is guaranteed.

Complexity Analysis

Like Tarjan's and Kosaraju's algorithms, Gabow's runs in optimal linear time:

$$\text{Time Complexity: } O(V + E) \qquad \text{Space Complexity: } O(V)$$

Because Gabow's algorithm avoids low-link array comparisons and assignment overhead, it often exhibits slightly smaller constant factors and fewer memory writes in benchmark tests.

Implementation

def gabow_scc(n, adj):
    """
    n: number of vertices (0-indexed).
    adj: adjacency list of directed graph.
    Returns list of SCCs (each SCC is a list of vertices).
    """
    sccs = []
    S = []  # Vertex stack
    P = []  # Boundary stack
    order = [0] * n
    counter = 0

    def dfs(u):
        nonlocal counter
        counter += 1
        order[u] = counter
        S.append(u)
        P.append(u)

        for v in adj[u]:
            if order[v] == 0:
                dfs(v)
            elif v in S_set:  # v is active on stack S
                while order[P[-1]] > order[v]:
                    P.pop()

        if P[-1] == u:
            P.pop()
            scc = []
            while True:
                node = S.pop()
                S_set.remove(node)
                scc.append(node)
                if node == u:
                    break
            sccs.append(scc)

    S_set = set()
    
    # Adjusted DFS wrapper using S_set for O(1) membership
    def dfs_fast(u):
        nonlocal counter
        counter += 1
        order[u] = counter
        S.append(u)
        S_set.add(u)
        P.append(u)

        for v in adj[u]:
            if order[v] == 0:
                dfs_fast(v)
            elif v in S_set:
                while order[P[-1]] > order[v]:
                    P.pop()

        if P[-1] == u:
            P.pop()
            scc = []
            while True:
                node = S.pop()
                S_set.remove(node)
                scc.append(node)
                if node == u:
                    break
            sccs.append(scc)

    for i in range(n):
        if order[i] == 0:
            dfs_fast(i)

    return sccs

# Example Graph
n = 5
adj = [[1], [2], [0, 3], [4], []]
print("SCCs (Gabow):", gabow_scc(n, adj))

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class GabowSCC {
    int n, counter;
    vector<vector<int>> adj;
    vector<int> order;
    vector<bool> inS;
    vector<int> S, P;
    vector<vector<int>> sccs;

    void dfs(int u) {
        order[u] = ++counter;
        S.push_back(u);
        inS[u] = true;
        P.push_back(u);

        for (int v : adj[u]) {
            if (order[v] == 0) {
                dfs(v);
            } else if (inS[v]) {
                while (order[P.back()] > order[v]) {
                    P.pop_back();
                }
            }
        }

        if (P.back() == u) {
            P.pop_back();
            vector<int> scc;
            while (true) {
                int node = S.back();
                S.pop_back();
                inS[node] = false;
                scc.push_back(node);
                if (node == u) break;
            }
            sccs.push_back(scc);
        }
    }

public:
    GabowSCC(int n, const vector<vector<int>>& adj) : n(n), adj(adj), counter(0) {
        order.assign(n, 0);
        inS.assign(n, false);
        for (int i = 0; i < n; ++i) {
            if (order[i] == 0) dfs(i);
        }
    }

    vector<vector<int>> getSCCs() { return sccs; }
};

int main() {
    int n = 5;
    vector<vector<int>> adj = {{1}, {2}, {0, 3}, {4}, {}};
    GabowSCC solver(n, adj);
    auto sccs = solver.getSCCs();

    cout << "SCCs found:\n";
    for (const auto& scc : sccs) {
        cout << "[ ";
        for (int v : scc) cout << v << " ";
        cout << "]\n";
    }
    return 0;
}

import java.util.*;

public class GabowSCC {
    private int n, counter;
    private List<List<Integer>> adj;
    private int[] order;
    private boolean[] inS;
    private Deque<Integer> S = new ArrayDeque<>();
    private Deque<Integer> P = new ArrayDeque<>();
    private List<List<Integer>> sccs = new ArrayList<>();

    public GabowSCC(int n, List<List<Integer>> adj) {
        this.n = n;
        this.adj = adj;
        this.order = new int[n];
        this.inS = new boolean[n];
        this.counter = 0;

        for (int i = 0; i < n; i++) {
            if (order[i] == 0) dfs(i);
        }
    }

    private void dfs(int u) {
        order[u] = ++counter;
        S.push(u);
        inS[u] = true;
        P.push(u);

        for (int v : adj.get(u)) {
            if (order[v] == 0) {
                dfs(v);
            } else if (inS[v]) {
                while (order[P.peek()] > order[v]) {
                    P.pop();
                }
            }
        }

        if (P.peek() == u) {
            P.pop();
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int node = S.pop();
                inS[node] = false;
                scc.add(node);
                if (node == u) break;
            }
            sccs.add(scc);
        }
    }

    public List<List<Integer>> getSCCs() { return sccs; }

    public static void main(String[] args) {
        int n = 5;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        adj.get(0).add(1);
        adj.get(1).add(2);
        adj.get(2).add(0);
        adj.get(2).add(3);
        adj.get(3).add(4);

        GabowSCC solver = new GabowSCC(n, adj);
        System.out.println("SCCs found: " + solver.getSCCs());
    }
}

Real-World Applications

Exercises

1. Trace Gabow's algorithm on a 4-cycle graph $0 \to 1 \to 2 \to 3 \to 0$. Show the contents of stacks $S$ and $P$ at every step.
2. Compare Gabow's 2-stack approach with Tarjan's 1-stack + lowlink approach.
3. Show how the output of Gabow's algorithm gives a topological ordering of the condensation DAG.
4. Challenge: Modify Gabow's algorithm to compute biconnected components on undirected graphs.

Limitations