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

A topological order linearizes a DAG so every prerequisite appears before its dependents. It directly models build dependencies, prerequisites, task scheduling, and spreadsheet recalculation. Python import execution also involves runtime code, caching, and circular-import behavior, so it is not simply one global 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).

DFS postorder is another standard method, but it must track unvisited, active, and finished states. Encountering an active node detects a cycle. Reversing postorder without cycle detection can produce a plausible but invalid result for a non-DAG.

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