Kosaraju and Tarjan

Two well-known methods find every strongly connected group in O(V + E) time. Kosaraju’s method uses two depth-first searches. Tarjan’s method uses one search and one extra number per vertex. Both read the finish order of depth-first search (GRPH-3).

Kosaraju: finish order, then turn round

1. Run a depth-first search over the whole graph (starting again from every vertex not yet reached), and list the vertices in the order they finish.
2. Reverse every edge.
3. Go through the vertices from the last to finish to the first. From each vertex that has no group yet, search the reversed graph, and give every vertex it reaches that has no group yet a new group number.

Each search in step 3 finds exactly one whole group. Step through the first variant of the figure.

Why each search finds one group

For a group X, let f(X) be the latest finish time of any vertex in X. The whole proof rests on one fact about the graph of groups (lesson 1).

Take the first vertex of X ∪ Y that the search reaches; call it x. There are two cases.

• x is in X. At that moment no vertex of X or Y is reached, and x reaches all of them (all of X inside its group, then the edge into Y, then all of Y). By the free-path fact of GRPH-3, every one of them ends up below x in the search, so each finishes before x. So x finishes last of all of them: f(X) = finish of x > f(Y).
• x is in Y. The search from x reaches all of Y, but none of X: if anything in Y reached X, X and Y would be one group (the edge X → Y already gives the way back). So all of Y finishes before the search ever reaches X, and every vertex of X finishes later. So f(X) > f(Y).

Now step 3. The vertex with the latest finish of all is in a group X whose f is the largest. By the key fact, no edge comes into X from another group, because that group would have a larger f. In the reversed graph that means no edge leaves X. So a search of the reversed graph from that vertex reaches exactly X: all of X (a group stays a group when every edge is reversed) and nothing else.

Then the method takes the next vertex with no group, by finish time. Its group X′ has the largest f among the groups left. Any edge into X′ from a group not yet found would break the key fact, so in the reversed graph the only edges leaving X′ lead to groups already found, and the search skips vertices that already have a group. By induction, every search finds exactly one group. The groups also come out in topological order: each group has no edges coming in from groups found later.

Cost: two searches over all vertices and edges, plus building the reversed graph: O(V + E) time and O(V + E) memory.

Tarjan: one search and a stack

Robert Tarjan’s method (1972) finds the groups during one depth-first search. Each vertex gets two numbers: index[v], its place in the order of discovery (1, 2, 3, …), and low[v], its low-link number. Each vertex is also pushed on a separate stack when it is reached, and stays there until its whole group is known.

# index[u]: when u was reached (0 = not yet); low[u]; on[u]: is u
# on the stack?; comp[u]: u's group; t and count: two counters.
    def visit(u):
        nonlocal t, count
        t += 1
        index[u] = low[u] = t
        stack.append(u); on[u] = True
        for v in adj[u]:
            if index[v] == 0:
                visit(v)
                low[u] = min(low[u], low[v])
            elif on[v]:                # v's group is not finished
                low[u] = min(low[u], index[v])
        if low[u] == index[u]:         # u is its group's first vertex
            while True:
                x = stack.pop(); on[x] = False
                comp[x] = count
                if x == u:
                    break
            count += 1

This is the main step of the method: one call per vertex, run from every vertex not yet reached. Setting up the lists and the outer loop is left to CONN-P2, which also needs a version without recursion and the groups in topological order. Step through the second variant of the figure. The tag on each junction reads index/low; the stack is beside the graph (under it on a phone).

The low-link rule

In each group, call the vertex the search reaches first the group’s head. By the free-path fact, the rest of the group ends up below the head in the search, so the head finishes last in its group.

low[u] is the smallest index the search can reach from u’s part of the search tree, using tree edges down and then one edge to a vertex that is still on the stack. A vertex is still on the stack exactly when its group is not finished, which means its head is still on the current path, above u or equal to u.

• If u is not a head, its head h is above u on the path. h reaches u, so u reaches h, and the path from u to h must leave u’s part of the tree by some edge into a vertex that is reached and still on the stack, with an index smaller than u’s. That edge lowers low somewhere under u, and the lower value is carried up to u. So low[u] < index[u].
• If u is a head, every vertex on the stack with a smaller index belongs to a different group above u. An edge from u’s part to such a vertex w would give a path u → … → w, and w is above u on the path, so w reaches u: they would be one group, a contradiction. So nothing lowers low[u] below index[u].

When a head u finishes, the vertices above it on the stack are exactly its group: they were pushed after u, while u was on the path, and every group found inside u’s part has already been popped. So popping down to u gives the group.

Why must the rule ask “is v still on the stack?”? An edge to a vertex whose group is finished leads into a group that cannot get back, and must be ignored. In the figure, F’s streets lead to E and G, both finished: F is a group on its own. Without the check, low[F] would drop to 3 and F would never be popped.

Many books write the edge rule as low[u] = min(low[u], low[v]) for every v on the stack. That also finds the right groups, though low then means something slightly different. The version above matches the proof.

Without recursion

Both methods are depth-first searches, and a path can be 100,000 vertices long, far beyond Python’s limit of about 1,000 nested calls (GRPH-3), and lower still in the browser. Use the stack of (vertex, iterator) pairs from GRPH-P3. For Tarjan, the work after a recursive call returns, low[u] = min(low[u], low[v]), moves to the moment v is popped from that stack: the vertex now on top is v’s parent. The stack of the method itself (the one holding unfinished groups) is a second, separate list.

Kosaraju needs the iterator form only in its first pass, where the finish order matters. The second pass only marks what it reaches, so a plain stack or a queue is enough.

Which one to use

• Kosaraju is easier to get right and to prove. It needs the reversed graph (twice the memory for edges) and two searches.
• Tarjan needs one search and no reversed graph, so it is usually faster. The low-link rule needs care.
• A third method, the path-based method of Cheriyan, Mehlhorn and Gabow, keeps two stacks and no low numbers. All three are O(V + E).
• In Python, the networkx library does this for you with its function strongly_connected_components. The practice pages do not have networkx, so write it yourself there.

Now try CONN-P2, Every group, in order.