Kosaraju's Algorithm

A Bit of History

Kosaraju's algorithm has one of the more unusual origin stories in this series: computer scientist S. Rao Kosaraju devised it around 1978, but never published it himself — it circulated as an unpublished course handout at Johns Hopkins University. Three years later, in 1981, Micha Sharir independently discovered and published an equivalent two-pass technique in a formal paper. The algorithm is now universally credited to both — "Kosaraju's algorithm" for the original unpublished insight, sometimes "Kosaraju-Sharir" in more careful references — a reminder that an idea circulating informally among students and colleagues can shape a field just as much as a published paper.

Working Principle

Recall from Part 8: a strongly connected component (SCC) is a maximal set of mutually reachable vertices, and collapsing SCCs produces a DAG (the condensation graph). Kosaraju's algorithm finds every SCC in two DFS passes:

1. Pass 1: run DFS on the original graph \(G\), recording each vertex's finish time (exactly the bookkeeping from Part 6).
2. Transpose: build \(G^T\), the graph with every edge reversed.
3. Pass 2: run DFS on \(G^T\), processing vertices in decreasing order of finish time from Pass 1. Each resulting DFS tree is exactly one SCC.

Worked Example

A graph with two SCCs: \(A \to B \to C \to A\) (a 3-cycle) and \(D \to E \to D\) (a 2-cycle), plus a single connecting edge \(C \to D\).

flowchart LR
    subgraph SCC1["SCC {A, B, C}"]
        A --> B --> C --> A
    end
    subgraph SCC2["SCC {D, E}"]
        D --> E --> D
    end
    C -->|"bridge edge"| D
            

Pass 1 (DFS on \(G\) from \(A\)) finishes \(D\) and \(E\) before \(A\), \(B\), \(C\) (since the traversal must go "downstream" through the bridge edge before backtracking). Pass 2 processes vertices in decreasing finish-time order — starting with \(A\) (or \(B\)/\(C\), whichever finished last) — and DFS on \(G^T\) from there can only reach \(\{A, B, C\}\), because the bridge edge \(C \to D\) is now reversed to \(D \to C\) and points the "wrong way." That first DFS tree is exactly SCC \(\{A,B,C\}\); a second DFS starting from the next unvisited highest-finish-time vertex recovers \(\{D,E\}\).

Why the Transpose Trick Works

The key fact, provable via the condensation-DAG structure from Part 8: processing vertices in decreasing finish-time order guarantees that the first unvisited vertex picked in Pass 2 always belongs to a source SCC of the condensation DAG (one with no incoming edges from other SCCs) — as seen from the transposed graph, which is exactly a sink SCC of the original condensation DAG. Because \(G^T\) reverses every edge, a DFS from this vertex can only reach vertices within its own SCC (any path leaving the SCC in \(G^T\) would have meant an incoming edge to that SCC from another one in \(G\), contradicting sink-ness). Removing that SCC and repeating the argument inductively covers every remaining SCC in turn.

Complexity Analysis

Two DFS passes plus building the transpose graph, all linear:

$$\text{Time: } O(V + E) \qquad \text{Space: } O(V + E) \text{ (storing both } G \text{ and } G^T\text{)}$$

Implementation

from collections import defaultdict

def kosaraju_scc(vertices, edges):
    """edges: list of (u, v) directed edges. Returns list of SCCs (each a list of vertices)."""
    adj = defaultdict(list)
    radj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        radj[v].append(u)

    # Pass 1: record finish order on G
    visited = set()
    finish_order = []

    def dfs1(u):
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                dfs1(v)
        finish_order.append(u)   # append on finish -> later entries finish later

    for v in vertices:
        if v not in visited:
            dfs1(v)

    # Pass 2: DFS on G^T in decreasing finish-time order
    visited.clear()
    sccs = []

    def dfs2(u, component):
        visited.add(u)
        component.append(u)
        for v in radj[u]:
            if v not in visited:
                dfs2(v, component)

    for v in reversed(finish_order):
        if v not in visited:
            component = []
            dfs2(v, component)
            sccs.append(component)

    return sccs

vertices = ["A", "B", "C", "D", "E"]
edges = [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D"), ("D", "E"), ("E", "D")]

print(kosaraju_scc(vertices, edges))   # [['A', 'C', 'B'], ['D', 'E']]  (order may vary within each SCC)

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
using namespace std;

void dfs1(string u, unordered_map<string, vector<string>>& adj,
          unordered_set<string>& visited, vector<string>& finishOrder) {
    visited.insert(u);
    for (auto& v : adj[u]) if (!visited.count(v)) dfs1(v, adj, visited, finishOrder);
    finishOrder.push_back(u);
}

void dfs2(string u, unordered_map<string, vector<string>>& radj,
          unordered_set<string>& visited, vector<string>& component) {
    visited.insert(u);
    component.push_back(u);
    for (auto& v : radj[u]) if (!visited.count(v)) dfs2(v, radj, visited, component);
}

int main() {
    unordered_map<string, vector<string>> adj = {
        {"A", {"B"}}, {"B", {"C"}}, {"C", {"A", "D"}}, {"D", {"E"}}, {"E", {"D"}}
    };
    unordered_map<string, vector<string>> radj;
    for (auto& [u, list] : adj) for (auto& v : list) radj[v].push_back(u);

    vector<string> vertices = {"A", "B", "C", "D", "E"};
    unordered_set<string> visited;
    vector<string> finishOrder;
    for (auto& v : vertices) if (!visited.count(v)) dfs1(v, adj, visited, finishOrder);

    visited.clear();
    reverse(finishOrder.begin(), finishOrder.end());
    int sccCount = 0;
    for (auto& v : finishOrder) {
        if (!visited.count(v)) {
            vector<string> component;
            dfs2(v, radj, visited, component);
            sccCount++;
        }
    }
    cout << "Number of SCCs: " << sccCount << endl;  // 2
    return 0;
}

import java.util.*;

class Kosaraju {
    static void dfs1(String u, Map<String, List<String>> adj, Set<String> visited, List<String> finishOrder) {
        visited.add(u);
        for (String v : adj.getOrDefault(u, List.of())) {
            if (!visited.contains(v)) dfs1(v, adj, visited, finishOrder);
        }
        finishOrder.add(u);
    }

    static void dfs2(String u, Map<String, List<String>> radj, Set<String> visited, List<String> component) {
        visited.add(u);
        component.add(u);
        for (String v : radj.getOrDefault(u, List.of())) {
            if (!visited.contains(v)) dfs2(v, radj, visited, component);
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> adj = new HashMap<>();
        adj.put("A", List.of("B")); adj.put("B", List.of("C"));
        adj.put("C", List.of("A", "D")); adj.put("D", List.of("E")); adj.put("E", List.of("D"));

        Map<String, List<String>> radj = new HashMap<>();
        for (var entry : adj.entrySet())
            for (String v : entry.getValue())
                radj.computeIfAbsent(v, k -> new ArrayList<>()).add(entry.getKey());

        List<String> vertices = List.of("A", "B", "C", "D", "E");
        Set<String> visited = new HashSet<>();
        List<String> finishOrder = new ArrayList<>();
        for (String v : vertices) if (!visited.contains(v)) dfs1(v, adj, visited, finishOrder);

        visited.clear();
        Collections.reverse(finishOrder);
        int sccCount = 0;
        for (String v : finishOrder) {
            if (!visited.contains(v)) {
                List<String> component = new ArrayList<>();
                dfs2(v, radj, visited, component);
                sccCount++;
            }
        }
        System.out.println("Number of SCCs: " + sccCount);  // 2
    }
}

Real-World Applications

Exercises

1. Trace Kosaraju's algorithm by hand on a 6-vertex graph with three SCCs of your own design, recording finish times explicitly.
2. Explain why processing Pass 2 in increasing (rather than decreasing) finish-time order would break the algorithm — construct a small counterexample.
3. Prove that the condensation graph built from Kosaraju's output is guaranteed to be a DAG, citing the Part 8 argument.
4. Challenge: Modify the implementation to also build the condensation graph explicitly (one node per SCC, edges between SCCs where original edges crossed between them), and verify it's acyclic on your test graph.

Limitations