Topological Sort

The 10-second versionCopy Anchor Link

A topological sort lines up the vertices of a directed graph so that every edge points forward in the list — every prerequisite comes before the thing that needs it. It's the answer to "in what order do I actually do these tasks?" The catch: it only exists if the graph is a DAG (directed and acyclic); a cycle makes a valid order impossible. There are two classic ways to get one — Kahn's algorithm, which repeatedly peels off a task nothing else is waiting on, and DFS, whose reverse finish order is itself a valid ordering.

Why this existedCopy Anchor Link

The problem is as old as planning: do things in an order that respects what they depend on. You can't install a package before its library. You can't hang a roof before the walls, or compile a header after the file that includes it.

Mathematically, the question "when does a consistent order even exist?" was framed surprisingly early. In 1930 the Czech mathematician Václav Jarník studied the necessary conditions for arranging a set of items so that every stated constraint is honoured — the seed of the whole idea.

The engineering push came decades later, from project management. In 1958 the US Navy's PERT (Program Evaluation and Review Technique) modelled a huge project as a network of tasks with dependencies, and needed to schedule them correctly. Suddenly the abstract ordering question had a deadline, a budget and a Polaris missile attached to it.

Arthur B. Kahn, at Bell Labs, gave the clean algorithm we still teach in 1962 ("Topological sorting of large networks"). And in 1972, as a side effect of his work on DFS, Tarjan showed that simply finishing a depth-first search and reversing the order produces a valid toposort almost for free.

Why it mattered then: before a shared algorithm, schedulers hand-sorted dependencies and broke whenever the graph changed. Kahn's method turned "figure out the order" into a mechanical sweep that a machine could re-run on every build — which is exactly what your compiler, package manager and CI box do today, thousands of times a day.

Inside the inventor's headCopy Anchor Link

Picture a build system in 1962 with a few thousand source files. The naive instinct is to sort them somehow — alphabetically, by size, by when they were edited — and compile in that order. It works until it doesn't: a file gets compiled before the header it #includes, and the build explodes. You can't fix it by shuffling; the order is the problem.

The pivot is a change of perspective. Instead of choosing an order, build it one honest step at a time. Look for a task with no unmet prerequisites — nothing that has to come before it. That task is safe to do right now, no matter what. Do it. Then cross it off, and any task that was only waiting on it loses one blocker. Repeat.

Watch the reasoning, including the escape hatch:

That dotted branch is the beautiful part: the algorithm detects its own impossibility. If you ever get stuck with tasks remaining but none of them unblocked, the survivors must be tangled in a cycle — a genuine deadlock. You don't need a separate cycle check; the failure is the check.

Tarjan's version is a completely different route to the same destination. Instead of building the order from the front, run a depth-first search and write each vertex down as it finishes. A vertex only finishes after everything it points to has finished, so the first-finishing vertices are the dependents and the last-finishing is the root. Flip that finish list, and dependencies tumble out on top. Two algorithms, one truth — but note the trap: Tarjan's version silently gives a wrong answer on a cyclic graph, so you must have already checked for cycles (previous page).

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

Kahn's algorithm, step by step:

The invariants that make it correctCopy Anchor Link

1. A zero-indegree vertex is always safe. Its indegree counts edges into it — unmet prerequisites. Zero means nothing must come before it, so placing it next can't violate any constraint.
2. Removing a vertex only removes real constraints. When we output u and decrement its neighbours' indegrees, we're striking off the exact prerequisites that just got satisfied — never any others.
3. If the output has fewer than V vertices, there's a cycle. Everything still stuck has a nonzero indegree that can never reach zero, because reaching zero needs a vertex outside the tangle, and a cycle has none. Leftover vertices are precisely the cyclic ones.
4. Reverse finish order is valid. For any edge u → v, DFS finishes v before u. So in the reversed list, u appears before v — exactly the ordering rule. This holds only for a DAG.

A worked traceCopy Anchor Link

A four-vertex dependency graph: 0 → 1, 0 → 2, 1 → 3, 2 → 3. Task 3 needs both 1 and 2; both need 0.

Indegrees: 0:0, 1:1, 2:1, 3:2. Only 0 is ready.

The output 0, 1, 2, 3 is valid; so is 0, 2, 1, 3. Whenever two tasks have no dependency between them, the algorithm may pick either — a topological order is not unique, and any of them is a correct answer.

It in codeCopy Anchor Link

Kahn's algorithm first. The queue can be an array with a head pointer, exactly like BFS:

function topoSort(adj) {  const n = adj.length;  const indeg = new Array(n).fill(0);  for (const nbrs of adj) for (const w of nbrs) indeg[w]++;  // count incoming edges  const queue = [];  for (let u = 0; u < n; u++) if (indeg[u] === 0) queue.push(u); // start from the sources  const order = [];  for (let head = 0; head < queue.length; head++) {    const u = queue[head];    order.push(u);                            // u's prerequisites are all done    for (const w of adj[u]) if (--indeg[w] === 0) queue.push(w);  }  return { order, isAcyclic: order.length === n };  // shorter order  →  a cycle}

And the DFS route, which adds something genuinely new: no indegree bookkeeping at all — just record finish order and reverse it. (Remember: it assumes the graph is already known to be acyclic.)

function topoSortDFS(adj) {  const n = adj.length;  const color = new Array(n).fill(0);           // 0 white, 1 gray, 2 black  const out = [];  const visit = (u) => {    color[u] = 1;                               // gray    for (const w of adj[u]) if (color[w] === 0) visit(w);    color[u] = 2;                               // black    out.push(u);                                // record on finish (post-order)  };  for (let u = 0; u < n; u++) if (color[u] === 0) visit(u);  return out.reverse();                         // reverse → prerequisites come first}

Cost tableCopy Anchor Link

Both algorithms are linear, and both must do the same amount of work — look at every vertex and every edge a constant number of times. There is no "best case": a dense dependency graph costs more than a sparse one, but neither algorithm can skip anything.

Where you meet it todayCopy Anchor Link

• Build systems. make, Bazel and Gradle read a dependency graph and produce a build order — that's a topological sort, recomputed whenever a file changes.
• Package managers. npm, cargo and apt figure out install order from "A requires B" — and if there's a cycle, they refuse, exactly as Kahn's leftover check predicts.
• Task and workflow schedulers. DAG-based engines like Airflow and Spark lineage schedules each job after the jobs it consumes.
• Spreadsheet recalculation. Excel evaluates cells in dependency order so that a formula runs after the cells it references.

The recognizable one is the "course schedule" problem — given prerequisites, is there an order that satisfies them all, and if so, what is it? It's a topological sort with a coat of paint:

// prereqs: pairs [a, b] meaning "b must come before a".function courseOrder(n, prereqs) {  const adj = Array.from({ length: n }, () => []);  const indeg = new Array(n).fill(0);  for (const [a, b] of prereqs) {    adj[b].push(a);                       // edge b → a    indeg[a]++;  }  const queue = [];  for (let u = 0; u < n; u++) if (indeg[u] === 0) queue.push(u);  const order = [];  for (let head = 0; head < queue.length; head++) {    const u = queue[head];    order.push(u);    for (const w of adj[u]) if (--indeg[w] === 0) queue.push(w);  }  return order;                           // shorter than n  →  circular prerequisite}

RecapCopy Anchor Link

• A topological order puts every prerequisite before the thing it feeds; it exists only for a DAG.
• Kahn's algorithm repeatedly outputs a zero-indegree vertex and decrements its neighbours — O(V + E), and a leftover count < V reveals a cycle for free.
• DFS gives another route: write vertices down in finish order and reverse it.
• The order is generally not unique — any valid interleaving of independent tasks is correct.
• You meet it in every build tool, package manager and workflow scheduler you use.

Next up: Union-Find (Disjoint Sets) — the near-constant-time structure behind "are these two in the same group?"