Topological Sort Explained

Topological sort produces a linear ordering of a graph’s nodes such that every directed edge points from an earlier node to a later one. In plain terms: if task B depends on task A, a topological sort guarantees A appears before B in the output. It only works on a directed acyclic graph (DAG) — a graph with directed edges and no cycles — because a cycle would mean two nodes each need to come before the other, which is impossible to satisfy.

Why it matters

Anything modeled as “this must happen before that” is a candidate for topological sort: build systems compiling files in dependency order, package managers installing libraries before the packages that need them, spreadsheet formulas recalculating in the right order, and course prerequisites in a class schedule. It’s also the reason monorepo build tools can figure out which packages to rebuild first, and why CI/CD pipelines can run independent jobs in parallel while keeping dependent jobs sequential.

Two ways to compute it

Kahn’s algorithm works from the “no incoming edges” end:

1. Compute the in-degree (number of incoming edges) for every node.
2. Put every node with in-degree 0 into a queue — these have no unmet dependencies.
3. Repeatedly pop a node from the queue, add it to the output, and decrement the in-degree of each of its neighbors.
4. Whenever a neighbor’s in-degree drops to 0, push it onto the queue.
5. If every node makes it into the output, you have a valid ordering. If some nodes are never added, the graph has a cycle — no valid topological order exists.

That cycle check is a free byproduct: Kahn’s algorithm doubles as cycle detection, which is exactly why dependency managers use it to catch circular dependencies.

DFS-based topological sort works from the other end:

1. Run a standard depth-first search from any unvisited node.
2. When a node has no more unvisited neighbors to explore, push it onto a stack.
3. Once DFS finishes exploring everything reachable, pop the stack — that order is a valid topological sort.

The intuition: a node only gets pushed onto the stack after everything reachable from it has already been pushed. So popping the stack naturally produces dependencies before dependents.

Both approaches run in O(V + E) time — linear in the number of nodes and edges — and both are correct; the choice mostly comes down to whether you also want the built-in cycle detection (Kahn’s) or you’re already doing a DFS pass for another reason.

Multiple valid orderings, and picking a canonical one

Because a DAG can have several valid topological orderings whenever some nodes have no dependency relationship to each other, systems that need a stable, reproducible output — the same input graph should always produce the same order across runs — typically break ties with a secondary rule, such as sorting nodes alphabetically among those with equal in-degree at each step of Kahn’s algorithm. Without a tie-breaking rule, two runs of the same algorithm over the same graph can legitimately produce different (but equally valid) orderings, which can be surprising if you’re expecting deterministic output from a deterministic-looking build.

A worked example

Say a build has four files: utils.js has no dependencies, auth.js depends on utils.js, api.js depends on both utils.js and auth.js, and app.js depends on api.js. A valid topological order is utils.js, auth.js, api.js, app.js — every dependency appears before anything that needs it. Note that a DAG can have more than one valid topological order; if two nodes have no dependency relationship to each other, their relative order in the output is interchangeable.

Task scheduling with parallelism

Beyond producing a single linear order, topological sort generalizes naturally to scheduling independent tasks in parallel: group nodes into “levels,” where level 0 contains every node with no dependencies, level 1 contains nodes whose dependencies are all in level 0, and so on. Everything within a level can run concurrently, since none of those nodes depend on each other — only the levels themselves need to execute in order. This is effectively what a build system or CI pipeline does when it runs independent compilation steps in parallel while still respecting the overall dependency graph; Kahn’s algorithm produces these levels almost for free, since each pass of “remove every current in-degree-0 node” is exactly one level.

What breaks it: cycles

If auth.js depended on api.js while api.js also depended on auth.js, there’d be no valid ordering — that’s a circular dependency. This is precisely the failure mode topological sort is used to catch before it causes real trouble, whether that’s an infinite build loop or a spreadsheet formula that references itself indirectly. Detecting the cycle early, at the graph-analysis stage, is far cheaper than debugging the resulting hang.

Related to, but different from, shortest-path algorithms

Topological sort answers “what order,” not “what’s the cheapest path.” Dijkstra’s algorithm and A* search find shortest paths through weighted graphs and work on graphs with cycles; topological sort ignores edge weights entirely and requires the graph to be acyclic. That said, topological order is a useful preprocessing step for shortest-path problems on DAGs specifically — once nodes are topologically sorted, you can compute shortest (or longest) paths in a single linear pass without the priority queue Dijkstra’s needs, because you already know every predecessor has been finalized before you reach a given node.

The takeaway

Topological sort orders a DAG’s nodes so dependencies always precede their dependents, computed in linear time with either Kahn’s algorithm (repeatedly removing in-degree-0 nodes) or a DFS post-order traversal. It’s the algorithm behind build systems, package managers, and task schedulers, and it doubles as cycle detection — if the algorithm can’t place every node, the dependency graph has a cycle that needs breaking before anything can run.