Kosaraju's Algorithm, in depth: the finish-time lemma, iterative two-pass SCC, output order and real uses

Strong components and the condensation

Write u ~ v when u reaches v and v reaches u. This relation is reflexive, symmetric and transitive, so it partitions the vertices; the classes are the SCCs. Contract each SCC to a single node and keep one edge between two components whenever some edge joins them, and you get the condensation. The condensation is always a DAG: if two components could reach each other, they would be one component.

That gives the plan. If we could visit components in an order where, whenever we start a search, no edge leads to an unvisited component, a plain search from any vertex would stay inside exactly one component. Kosaraju gets that order from depth-first finish times. A refresher on DFS mechanics is in BFS and DFS.

The finish-time lemma

Run a full DFS on G, restarting from unvisited vertices until all are visited, and record for each vertex the time it finishes, after all its descendants. For a component C let f(C) be the largest finish time of any vertex in C.

Lemma. If G has an edge from a vertex in component C to a vertex in a different component D, then f(C) is greater than f(D).

Proof. Consider which of the two components the DFS enters first. Case 1: it enters C first, at vertex x. At that moment nothing in C or D is visited, and every vertex of C and D is reachable from x (all of C directly, all of D through the edge into D). By the white-path property of DFS, all of them become descendants of x, so they finish before x does, and f(C) equals x's finish time, which is greater than f(D). Case 2: it enters D first, at y. Every vertex of D is reachable from y and finishes before y finishes. No vertex of C is reachable from D, otherwise C and D would be one component, so no vertex of C is visited while y is active. All of C is visited later and finishes later, so f(C) is greater than f(D).

Read the lemma backwards: the vertex with the largest finish time overall lies in a component that no other component has an edge into, a source of the condensation.

Why the second pass uses the transpose

Searching G from that source component would leak into everything downstream. So reverse every edge. The transpose G^T has the same SCCs, since mutual reachability is symmetric, but every condensation edge points the other way. The source component of G is a sink in G^T: a search started there in G^T reaches exactly its own component.

Now repeat. Remove that component and take the unvisited vertex with the next-largest finish time. By the lemma, every edge of G^T leaving its component goes to a component with a larger f, which was already found and marked visited. So the second search also stays inside one component. Induction on the number of components finishes the proof.

KOSARAJU(G):
    order = []                       # vertices in increasing finish time
    for v in V: if not seen(v): DFS(G, v) appending v to order when it FINISHES
    build G^T
    clear seen
    for v in reversed(order):        # decreasing finish time
        if not seen(v):
            component = all vertices reached from v in G^T among unseen ones
            emit component           # any traversal works here: BFS, DFS, stack

Output order: topological, sources first

The components are emitted in decreasing order of f, and the lemma says every condensation edge goes from a larger f to a smaller one. So the emission order is a topological order of G's condensation, sources first. Tarjan's algorithm produces the opposite, reverse topological order, because it emits a component when its root finishes. Neither needs a separate topological sort of the condensation; you just need to know which direction you are holding. For ordering in general see topological sort two ways.

Whether you want that order or its reverse depends on what an edge means. If u to v means "u imports v", sources are the top-level modules and dependencies come later, so a build processes Kosaraju's output in reverse. If u to v means "u must run before v", Kosaraju's order is already the schedule.

An iterative implementation that is actually correct

Recursive DFS overflows on deep graphs: a 1,000,000-vertex path is a 1,000,000-frame recursion. Raising Python's recursion limit is not a fix: on older CPython versions the C stack can overflow and crash the process, and on any version it ties correctness to a process-wide setting and a large frame footprint. Pass 1 must be iterative, and it must record true finish times. The tempting version, pop a vertex, mark it, push all its neighbours, append it to the order, records a pre-order, not a post-order, and it passes many small tests.

Here is a minimal graph that breaks it: edges a to b, b to c, c to b. The SCCs are {a} and {b, c}. The naive order is a, b, c, so pass 2 starts from c in the transpose, where c reaches b and b reaches a, and it merges all three into one component. True post-order finishes c, then b, then a, so pass 2 starts from a, which reaches nothing in the transpose, and the answer is correct. Keep a frame of (vertex, next edge index) instead:

def to_csr(n, edges, reverse=False):
    '''Compressed sparse row adjacency in O(n + m): offsets and targets arrays.'''
    deg = [0] * (n + 1)
    for u, v in edges:
        deg[(v if reverse else u) + 1] += 1
    for i in range(n):
        deg[i + 1] += deg[i]
    pos, tgt = deg[:-1].copy(), [0] * len(edges)
    for u, v in edges:
        s, t = (v, u) if reverse else (u, v)
        tgt[pos[s]] = t
        pos[s] += 1
    return deg, tgt


def kosaraju(n, edges):
    off, adj = to_csr(n, edges)
    roff, radj = to_csr(n, edges, reverse=True)       # transpose by counting sort
    seen, order = [False] * n, []
    for s in range(n):                                # pass 1: true post-order
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, off[s])]
        while stack:
            u, i = stack[-1]
            if i < off[u + 1]:
                stack[-1] = (u, i + 1)
                v = adj[i]
                if not seen[v]:
                    seen[v] = True
                    stack.append((v, off[v]))
            else:
                stack.pop()
                order.append(u)                       # u FINISHES here
    comp, comps = [-1] * n, []
    for s in reversed(order):                         # pass 2: any traversal
        if comp[s] != -1:
            continue
        cid, todo, members = len(comps), [s], []
        comp[s] = cid
        while todo:
            u = todo.pop()
            members.append(u)
            for i in range(roff[u], roff[u + 1]):
                v = radj[i]
                if comp[v] == -1:
                    comp[v] = cid
                    todo.append(v)
        comps.append(members)
    return comp, comps        # comps in topological order of the condensation

Pass 2 is safe with a simple stack because it only needs the set of reachable vertices, not an order. Assigning comp when a vertex is pushed, rather than popped, keeps each vertex on the stack at most once.

Cost and memory

Both passes touch each vertex and edge a constant number of times, so time is O(V + E). Memory is the graph, its transpose, a finish-order array and a component array. With CSR and 32-bit integers that is roughly 8 bytes per edge for the two target arrays plus 16 bytes per vertex for offsets, order and labels, before Python's object overhead; in Python, use the array module or NumPy for anything large. The transpose doubles edge storage, which is Kosaraju's main cost relative to Tarjan. In exchange, both passes are plain sequential sweeps, the second pass can use any traversal, and the code has no low-link bookkeeping to get wrong.

On very large graphs, practitioners often trim first: a vertex with zero in-degree or zero out-degree is its own SCC, and removing such vertices repeatedly shrinks typical real-world graphs a lot before any search runs. Parallel SCC algorithms commonly use a forward-backward scheme instead of DFS order: the vertices both forward-reachable and backward-reachable from a pivot form its SCC, and the remaining three sets can be processed independently.

Worked example: an import graph

Eight modules, with an edge meaning "imports": a to b, b to c, c to a, b to d, d to e, e to f, f to d, g to f, g to h, h to g. Adjacency lists are in that order.

Pass 1 starts at a: a, b, c; c's only edge goes back to a, so c finishes first. Back at b, the next edge leads to d, e, f; f's edge returns to d, so f, e and d finish, then b, then a. g is still unvisited: its edge to f is already done, h's edge returns to g, so h finishes, then g. Finish order: c, f, e, d, b, a, h, g.

Pass 2 walks that list backwards on the transpose. From g it reaches h (the transpose of h to g) and nothing else, since g to f reversed is an edge out of f, not g: component {g, h}. Next unvisited is a: a reaches c, c reaches b, and b's transpose edge goes to a: {a, b, c}. Then d reaches f, f reaches e, and f's edge to g is already labelled: {d, e, f}.

The output {g, h}, {a, b, c}, {d, e, f} is a topological order of the condensation: both cycles feed into {d, e, f}. Each component with more than one module is an import cycle to report, and building in reverse emission order compiles {d, e, f} before anything that imports it.

Where it is used

• Dependency hygiene: report import or build-target cycles as whole components, which is more actionable than one cycle at a time.
• Compilers and type checkers: group mutually recursive functions or definitions so they are analysed together, in dependency order.
• Datalog and rule engines: stratify rules by component of the predicate dependency graph to evaluate recursion and check negation.
• Markov chains: components with no outgoing condensation edge are the closed communicating classes.
• Satisfiability: 2-SAT reduces to SCCs on the implication graph; the details are on the Tarjan page.

If you only need to know whether a cycle exists, a single DFS with three colours is enough. Use SCCs when you need to know which vertices form the cycles and how the cycles relate to each other.

Testing it

Test against a brute-force oracle: on random graphs of up to 12 vertices, compute reachability with a breadth-first search from every vertex, and check that u and v share a component exactly when each reaches the other. Assert that for every edge, the source component is not emitted after the target component, which checks the order claim. Include the three-vertex graph from the iterative section, a graph with self-loops and parallel edges, a graph with no edges, and a 1,000,000-vertex path to prove neither pass recurses.

Kosaraju or Tarjan?

If your graph store keeps both directions anyway, such as many graph databases and the CSR pair above, Kosaraju's extra memory disappears and its simplicity wins. If memory is tight and only forward edges exist, use Tarjan. For undirected cut structure, look at bridges and articulation points instead.

What to do next

1. Implement the iterative version above and run it on the three-vertex graph a to b, b to c, c to b to confirm it returns two components.
2. Write the brute-force reachability oracle and the edge-order assertion, and run a few thousand random graphs.
3. Decide what an edge means in your domain and whether you need the emission order or its reverse.
4. Store graphs in CSR with both directions if you will run SCCs repeatedly.
5. Apply it to your own codebase's import graph and list every component with more than one module.