Strongly Connected Components (Kosaraju)

What is a strongly connected component?

In a directed graph, u can reach v does not mean v can reach u. A strongly connected component (SCC) is a maximal set of vertices in which every vertex can reach every other one. Every vertex is in exactly one SCC; a vertex on no cycle forms an SCC on its own.

The example graph has 8 vertices and 13 edges and four components:

Component	Why
{a, b, e}	a → b → e → a is a cycle
{c, d}	c → d → c
{f, g}	f → g → f
{h}	h is on no cycle

SCCs show up in web graphs (groups of pages that link to each other), in social networks, in deadlock detection (a cycle in a wait-for graph) and in 2-SAT solvers. Compilers use them to find mutually recursive functions.

Kosaraju’s algorithm

1. DFS over the whole graph; push every vertex on a stack when it FINISHES
2. reverse every edge
3. while the stack is not empty:
       pop v; if v is unvisited, DFS from v in the reversed graph
       every vertex this DFS reaches is one SCC

Pass 1: finish order

The DFS starts at a (alphabetical order) and follows edges in alphabetical order: a → b → c → d → h. h has no way out, so it finishes first, then d. Back at c it explores g → f, and f, g and c finish; then e (after visiting nothing new) and finally b and a. The finish order is

h, d, f, g, c, e, b, a        (a finished last, so it is on top of the stack)

Why the finish order matters

Shrink every SCC to a single node and you get the component graph, which is always a DAG:

{a, b, e} → {c, d} → {f, g} → {h}        (plus {a, b, e} → {f, g} and {c, d} → {h})

Key fact: the vertex that finishes last in pass 1 lies in a source component of this DAG, one with no incoming edges from other components. Here that is a, in {a, b, e}.

Pass 2: reversed graph, latest finisher first

Now reverse every edge. Each component is still strongly connected (its cycles just run the other way), but every edge between components now points towards the source components.

• Pop a and DFS in the reversed graph: a ← e ← b. It reaches exactly {a, b, e}. It cannot go further, because the edges b → c and b → f now point into b.
• Pop b and e: already visited. Pop c: the DFS finds {c, d} (the edge into b leads to a component that is done).
• Pop g: it finds {f, g}. Pop h: {h} on its own.

Each DFS of pass 2 is trapped inside exactly one component, so each one finds exactly one SCC.

Kosaraju versus Tarjan

	Kosaraju	Tarjan
Depth-first searches	2	1
Needs the reversed graph	yes	no
Extra bookkeeping	a stack of finish times	discovery index and low-link per vertex, plus a stack
Running time	O(V + E)	O(V + E)
Order of the output	components in topological order of the DAG	components in reverse topological order

Kosaraju is easier to understand and prove; Tarjan uses one pass and is usually a little faster.

Code

EDGES = [('a', 'b'), ('b', 'c'), ('b', 'e'), ('b', 'f'), ('c', 'd'), ('c', 'g'), ('d', 'c'), ('d', 'h'),
         ('e', 'a'), ('e', 'f'), ('f', 'g'), ('g', 'f'), ('g', 'h')]
NODES = sorted({v for e in EDGES for v in e})

def adjacency(edges):
    adj = {v: [] for v in NODES}
    for u, v in edges:
        adj[u].append(v)
    return {v: sorted(n) for v, n in adj.items()}

def kosaraju(edges):
    # pass 1: DFS on the graph, remember the order in which vertices FINISH
    adj, seen, finished = adjacency(edges), set(), []
    def dfs1(u):
        seen.add(u)
        for v in adj[u]:
            if v not in seen:
                dfs1(v)
        finished.append(u)                      # u is done: all it can reach has been explored
    for v in NODES:
        if v not in seen:
            dfs1(v)
    # pass 2: DFS on the REVERSED graph, starting from the latest finisher
    radj, seen, components = adjacency([(v, u) for u, v in edges]), set(), []
    def dfs2(u, comp):
        seen.add(u)
        comp.append(u)
        for v in radj[u]:
            if v not in seen:
                dfs2(v, comp)
    for v in reversed(finished):
        if v not in seen:
            comp = []
            dfs2(v, comp)
            components.append(sorted(comp))
    return finished, components

finished, components = kosaraju(EDGES)
print('finish order:', finished)
# finish order: ['h', 'd', 'f', 'g', 'c', 'e', 'b', 'a']
print('components:  ', components)
# components:   [['a', 'b', 'e'], ['c', 'd'], ['f', 'g'], ['h']]
which = {v: i for i, c in enumerate(components) for v in c}
dag = sorted({(which[u], which[v]) for u, v in EDGES if which[u] != which[v]})
print('component DAG:', [(components[a], components[b]) for a, b in dag])
# component DAG: [(['a', 'b', 'e'], ['c', 'd']), (['a', 'b', 'e'], ['f', 'g']), (['c', 'd'], ['f', 'g']), (['c', 'd'], ['h']), (['f', 'g'], ['h'])]

networkx.strongly_connected_components returns the same four sets. For very deep graphs, replace the recursion with an explicit stack, because Python’s recursion limit is about 1000.

Common mistakes

• Running pass 2 on the original graph. Then the DFS from a would reach every vertex and report one big component.
• Using the wrong order in pass 2. Start from the vertex that finished last, not first.
• Using discovery time instead of finish time. The proof relies on finish times.
• Thinking an SCC needs at least two vertices. A vertex on no cycle is a component by itself, like h.
• Confusing SCCs with connected components of an undirected graph. Those ignore edge directions and can be found with a single BFS, DFS or union–find.