Kosaraju vs Tarjan Visualization | Strongly Connected Components

The idea: two ways to find the same components

A strongly connected component (SCC) of a directed graph is a largest set of vertices that can all reach each other. Both algorithms on this page find every SCC in O(V + E) time, and both are built on depth-first search. They differ in how much work they repeat and what they keep in memory. The page runs them on the same graph, one unit of work per Step in each lane, so the lane with less work finishes first.

Kosaraju: DFS on G records the finish order, then every edge is reversed, then a DFS on the reversed graph in decreasing finish order gives one SCC per tree, looking at 2E edges. Tarjan: one DFS on G keeps index, low and a stack, and pops an SCC whenever low equals index, looking at E edges. — Kosaraju runs two plain DFS passes with a reversal in between; Tarjan does the same job in one DFS by keeping two numbers per vertex and a stack.

Kosaraju: two passes and a reversed graph

Pass 1 runs a full DFS on G and writes each vertex onto a finish list when its call returns. The last vertex to finish always lies in a "source" SCC, one that no other SCC points into. Then the algorithm builds the transpose G^T, the same graph with every edge reversed; it has exactly the same SCCs. Pass 2 takes vertices from the end of the finish list and starts a DFS on G^T from each one that has no component yet. In G^T the edges that left the source SCC now point into it, so the DFS cannot escape: every tree it grows is exactly one SCC. The single-concept page is Connected Components (Kosaraju).

Tarjan: one pass with low-links

Tarjan's DFS gives each vertex an index (the order it is reached) and a low value: the smallest index it can reach through its DFS subtree plus one more edge to a vertex that is still on the stack. Every visited vertex is pushed on that stack. When a vertex finishes with low == index, nothing below it reaches higher up, so it is the root of an SCC and the stack is popped down to it. The canvas shows index/low next to each vertex. The single-concept page is Strongly Connected Components (Tarjan).

What the scoreboard counts

Demo	SCCs	Edges examined (K / T)	Steps (K / T)	Extra memory, words (K / T)
8-node graph	{A,B,E} {C,D} {F,G} {H}	26 / 13	59 / 36	29 / 30
A DAG	8 single vertices	22 / 11	55 / 34	27 / 29
One big cycle	{A..H}	20 / 10	53 / 33	26 / 32
Forgets to reverse	Kosaraju: 1 ✗, Tarjan: 4 ✓	26 / 13	59 / 36	29 / 30

Edges examined is always 2E for Kosaraju (every edge once per pass) and E for Tarjan. Extra memory is a rough count of words beyond the graph itself: Kosaraju stores the reversed copy (E edges), the finish list and a visited flag (E + 2V); Tarjan stores index, low and on-stack per vertex plus the stack at its tallest (3V + stack). On these sparse graphs Kosaraju's copy is small, so it wins memory, most clearly on the big cycle, where Tarjan's stack holds all 8 vertices (Demo: one big cycle, one SCC). On a dense graph, where E is many times V, the copy dominates and Tarjan uses far less.

Order of the output

Shrink every SCC to one node and you get the condensation, which is always a DAG. Kosaraju emits the SCCs in topological order of that DAG (sources first); Tarjan emits them in reverse topological order (sinks first), because an SCC is popped only after every SCC it points to is done. On a DAG every SCC is one vertex, so this is visible directly: Kosaraju lists A E B F C G D H, a topological order, and Tarjan the reverse (Demo: a DAG, every SCC is one vertex). See Topological Sort (DFS), which uses the same finish-order trick as Kosaraju's pass 1.

The condensation of the 8-node example: {A,B,E} points to {C,D} and {F,G}, {C,D} points to {F,G} and {H}, {F,G} points to {H}. A DFS on G from A, the last vertex to finish, follows those edges into every component and returns all 8 vertices, which is wrong. On the reversed graph the edges point into {A,B,E}, so the DFS from A stays inside {A,B,E}. — Pass 2 starts at the source SCC. On G its edges lead out into every other SCC; on the reversed graph they lead in, so the DFS stays inside one SCC.

When to pick which

	Kosaraju	Tarjan
Passes over the edges	2 (plus building the reversed graph)	1
State per vertex	visited flag, finish list	index, low, on-stack, stack
Extra memory	a copy of all E edges (unless in-edges are stored anyway)	O(V)
Output order	topological	reverse topological (what 2-SAT wants)
Easy to get right	yes: two textbook DFS passes	the low-link rule is subtle
Pick it when	the graph already stores in-edges, or clarity matters most	speed and memory matter, or the graph is huge or streamed once

Common mistakes

Forgetting to reverse the graph. Pass 2 on G starts in the source SCC and walks out of it into everything downstream; on the 8-node graph it returns all 8 vertices as one "component" (Demo: Kosaraju forgets to reverse).
Using the wrong order in pass 2. It must be decreasing finish time (the end of the finish list), not discovery order or A, B, C.
In Tarjan, updating low from a vertex that is not on the stack. An edge into a finished SCC must be ignored, or two SCCs merge.

What the page leaves out

Both algorithms are shown recursively, on one small graph at a time, with neighbours tried in alphabetical order. The page leaves out iterative versions (deep recursion overflows the call stack on large graphs), Pearce's variant of Tarjan that saves the on-stack bit, the path-based algorithms of Gabow and Cheriyan–Mehlhorn, parallel and external-memory SCC algorithms, and the real cost of memory access, which on big graphs often matters more than edge counts.