Topological Sort: Ordering by Dependency

"You can't put on your shoes before your socks. Topological sort is the algorithm that, given a tangle of 'X must come before Y' rules, hands you a valid order to do everything — or tells you the rules contradict themselves."

The Problem

Given a directed acyclic graph (DAG) where an edge X→Y means "X must come before Y," a topological sort produces a linear ordering of all nodes such that every node appears after all its prerequisites. This is the math behind a thousand everyday systems: build tools compiling files in dependency order, package managers installing dependencies first, course prerequisites, task schedulers, spreadsheet cells recalculating in the right order, even the order Python imports your modules. Whenever the question is "what's a valid order to do these interdependent things?", it's topological sort.

Kahn's Algorithm: Peel Off the Ready Ones

The most intuitive method works by in-degree — how many prerequisites each node still has unmet. Repeatedly: take any node with zero remaining prerequisites (it's ready to go), output it, and remove its outgoing edges (decrementing its neighbors' in-degrees, possibly making them ready too). Use a queue to hold the ready nodes. Keep going until everything's output. It's BFS-flavored: process the frontier of currently-doable tasks, which unlocks the next frontier. O(V + E).

The alternative is DFS post-order: DFS the graph, and as each node finishes (all its descendants done), prepend it to the answer. Reverse the post-order and you have a valid topological order. Both are standard; Kahn's is often easier to reason about because 'zero prerequisites = ready' maps so cleanly to intuition.

Topological sort linearizes a DAG so every node follows its prerequisites. Kahn's algorithm repeatedly outputs zero-in-degree (ready) nodes via a queue; DFS post-order reversed also works. Both O(V+E) — and both detect cycles for free.

The Bonus: Cycle Detection

Topological sort only works on a DAG — a graph with no cycles. And it tells you when that's violated: in Kahn's algorithm, if you run out of zero-in-degree nodes before outputting them all, the leftover nodes form a cycle (a mutual dependency: A needs B, B needs A — neither can ever be 'ready'). That's a real, useful diagnostic: a build system reporting "circular dependency detected" is a failed topological sort. So the algorithm doesn't just order the doable — it proves whether a valid order exists at all.

Pippa's Confession

The first time a build failed with "circular dependency," I had no idea what the tool was even doing. Later, learning Kahn's algorithm, it clicked retroactively: the build was attempting a topological sort of my modules, ran out of zero-prerequisite files, and the leftovers were two modules importing each other. The error wasn't mysterious tooling — it was this exact algorithm telling me my dependency graph had a cycle. Understanding the algorithm explained an error I'd been cargo-culting around for years.

Code

Kahn's algorithm + built-in cycle detection·python

from collections import deque

# Kahn's algorithm: output zero-in-degree nodes until none remain.
def topo_sort(graph):
    # in-degree = number of prerequisites each node still has
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    # start with everything that has no prerequisites
    q = deque([u for u in graph if indeg[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)               # u is ready -> output it
        for v in graph[u]:
            indeg[v] -= 1             # one prerequisite of v satisfied
            if indeg[v] == 0:         # v now has no unmet prerequisites
                q.append(v)
    if len(order) != len(graph):
        raise ValueError("cycle detected — no valid ordering exists")
    return order

# 'app' needs backend+frontend; both need database.
deps = {"database": ["backend", "frontend"], "backend": ["app"],
        "frontend": ["app"], "app": []}
print(topo_sort(deps))   # ['database', 'backend', 'frontend', 'app'] (a valid order)

# A cycle has no valid order:
cycle = {"a": ["b"], "b": ["a"]}
try: topo_sort(cycle)
except ValueError as e: print(e)   # cycle detected — no valid ordering exists

Exercise

Courses: Calculus requires Algebra; Physics requires Calculus and Algebra; Chemistry requires Algebra. Using Kahn's algorithm (start from zero-prerequisite courses), produce one valid order to take them all. Then: if someone added 'Algebra requires Physics', what would Kahn's algorithm report, and why?

Hint

Zero-prereq start: Algebra. After Algebra: Calculus and Chemistry become ready; then Physics once Calculus is done. A valid order: Algebra, Calculus, Chemistry, Physics. Adding 'Algebra requires Physics' makes a cycle (Algebra↔Physics via Calculus) — Kahn's runs out of zero-in-degree nodes and reports a cycle.

The Problem

Kahn's Algorithm: Peel Off the Ready Ones

The Bonus: Cycle Detection

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0