What is topological sort?
Topological sort orders the nodes of a directed acyclic graph so that every edge points from earlier
to later in the ordering. Whenever some tasks must happen before others — build a library before the app
that uses it, take Algebra before Calculus — a topological sort finds a sequence that respects every one of
those "must come before" rules at once.
- DAG
- A directed acyclic graph — arrows only, and no path ever loops back to where it started
- In-degree
- How many edges point into a node — how many prerequisites it's still waiting on
- Topological order
- A sequence where every edge points from an earlier node to a later one
Why topological sort at all?
Picture getting dressed. Socks come before shoes, a shirt comes before a jacket — but there's no single required order for everything. Shirt and socks don't care about each other at all.
Topological sort doesn't invent one true order. It just peels off whatever has no unmet requirements left, puts it down, and repeats — any sequence that falls out is valid.
Shoes needs socks. Jacket needs shirt and pants. Nothing else depends on anything.
What kinds of problems does it solve?
Four common shapes. Every one of them is really "peel off what's ready" — what changes is where the dependency graph comes from and what you do with the order once you have it.
Course scheduling
Each course lists its prerequisites. Build a graph where an edge points from a prerequisite to the course that needs it, then peel off courses whose prerequisites are all already taken.
Algebra is the only course with no prerequisites — it has to go first.
Build order
A project depends on some libraries, which depend on others. Compile the dependencies before the things that import them — exactly a topological sort over the dependency graph.
main imports both lib and util, so it has to wait for both.
Recovering an unknown order
Given words already sorted by some unknown alphabet, the first letter where two neighboring words differ tells you one letter comes before another. Collect those edges, then sort them.
Comparing adjacent words letter by letter gives the edges: w→e, e→r, r→t, t→f.
Finding nodes that avoid every cycle
A node is "safe" if every path out of it eventually dead-ends instead of looping forever. Peel off terminal nodes first, then anything whose neighbors are all already known safe.
X and Y only ever point at each other — neither can be resolved as safe.
Two ways to get there
Same guarantee, two different mechanisms: one peels off ready nodes with a queue, the other walks the graph and records finish order, then reverses it.
Kahn's algorithm
Count every node's in-degree. Push anything at zero into a queue. Pop a node, add it to the
order, and decrement its neighbors' in-degrees — any that hit zero join the queue.
S needs both Q and R to finish before its in-degree reaches zero.
function topoSort(nodes: string[], edges: [string, string][]): string[] {
const inDegree = new Map(nodes.map((n) => [n, 0]));
const graph = new Map(nodes.map((n) => [n, [] as string[]]));
for (const [from, to] of edges) {
graph.get(from)!.push(to);
inDegree.set(to, inDegree.get(to)! + 1);
}
const queue = nodes.filter((n) => inDegree.get(n) === 0);
const order: string[] = [];
while (queue.length > 0) {
const node = queue.shift()!;
order.push(node);
for (const neighbor of graph.get(node)!) {
inDegree.set(neighbor, inDegree.get(neighbor)! - 1);
if (inDegree.get(neighbor) === 0) queue.push(neighbor);
}
}
return order.length === nodes.length ? order : []; // shorter than n means a cycle
}
DFS-based
Run a depth-first search. The moment a node has no more unvisited neighbors to explore, it's finished — prepend it to the result. A node can only finish after everything it points to has.
S finishes first, but ends up last in the order — finish order gets reversed.
function topoSort(nodes: string[], graph: Map): string[] {
const visited = new Set();
const order: string[] = [];
function visit(node: string): void {
if (visited.has(node)) return;
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
visit(neighbor);
}
order.unshift(node); // prepend — this node is now fully finished
}
for (const node of nodes) {
visit(node);
}
return order;
}
Where it works — and where it breaks
Topological sort leans on one non-negotiable assumption: the graph is a DAG. The moment there's a cycle, no ordering can satisfy every edge, because some node would have to come before itself.
Works on a DAG
Every node eventually reaches an in-degree of zero, because the graph has no cycles to keep its prerequisites permanently unmet. Peeling never gets stuck.
Breaks on a cycle
A→B→C→A means every node is waiting on a node that's waiting on it. No node ever reaches in-degree zero, so the queue starts empty and stays that way — nothing can ever be safely placed.