Topological sort

What this chapter covers

Topological sort answers the most common question you can ask about a graph of dependencies: given a pile of tasks where some must happen before others, what's a valid order to do them all? If your build system has to compile a library before the program that links it, if a course has prerequisites, if a spreadsheet cell depends on other cells, you have a directed graph and you need an ordering where every arrow points forward — every prerequisite before the thing that needs it. That ordering is a topological sort, and it exists exactly when the graph has no cycle (nothing can go first if two tasks each wait on the other). This chapter builds the two classic algorithms — one born from BFS, one from DFS — shows both are the last two chapters wearing new hats, and measures just how hard the problem is to solve by guessing: with a dozen dependencies, only about one random order in seven hundred is valid.

A bit of history

The problem is ancient in spirit — ordering tasks by dependency is as old as project planning — but the two algorithms have clear origins. In 1962 Arthur Kahn published the in-degree-peeling method in a paper on organizing the terms of a large computer program so each was defined before use; it's the "remove anything with no remaining prerequisites, repeat" algorithm, and it's still called Kahn's algorithm. The depth-first version came out of Robert Tarjan's early-1970s work on DFS-based graph algorithms, where he observed that the order in which DFS finishes nodes, reversed, is a topological order — a two-line addition to the depth-first search of the last chapter. Donald Knuth also treated the problem in detail in The Art of Computer Programming, tying it to the theory of partial orders: a topological sort is exactly a linear extension of a partial order, a way to flatten "some things come before others" into "here is one full sequence." Both algorithms are linear, both are still standard, and which one a library uses is mostly taste — Python's graphlib uses the DFS approach.

The intuition

Kahn's algorithm thinks like a project manager. Look at all the tasks and find the ones with no unmet prerequisites — in graph terms, the nodes with in-degree zero, no arrows pointing at them. Any of those can go first, so pick one, mark it done, and cross it off as a prerequisite everywhere: each task that was waiting on it now needs one fewer thing, and some of them may drop to zero unmet prerequisites and become available themselves. Repeat until everything is placed. If you ever get stuck — tasks remain but none has in-degree zero — those leftover tasks form a cycle, each waiting on another, and no valid order exists.

The DFS algorithm thinks backward instead. A task belongs after everything it depends on, so run a depth-first search and, the moment a node is fully finished (every task reachable from it is done), push it onto a list. A node finishes only after all its dependents further down have finished, so the list comes out in reverse dependency order — flip it and every arrow points forward. It's the exact DFS from last chapter with one line added at the finish point, and the same three-color scheme that detected cycles there detects them here: if DFS finds an edge back to a node still open on the stack, there's a cycle and no topological order.

Complexity: how it scales

Both algorithms are $O(V + E)$: Kahn's touches every node once as it's peeled and every edge once as it decrements in-degrees; the DFS version visits every node and edge once and appends to the finish list in $O(1)$. Space is $O(V)$ for the in-degree array or the color/finish arrays. There's no clever way to beat linear — you must at least read every dependency. The interesting number isn't the algorithm's speed but the size of the problem it's solving, which the face-off makes vivid: how often does a random ordering happen to satisfy all the constraints?

With nine tasks and twelve dependency edges, only about 0.135% of random orderings were valid — one in roughly seven hundred — and that fraction plummets as dependencies pile up, because each edge roughly halves the survivors. A topological sort finds a valid order every single time, in linear time, no guessing. That's the whole value proposition: the space of valid orders is a vanishing needle in the haystack of all orders, and topological sort walks straight to one. For a real build graph with thousands of edges, the fraction of valid random orders is so close to zero that you'd never stumble on one by chance in the lifetime of the universe — yet the algorithm produces one instantly.

What it's good at, what it isn't

Topological sort is the right tool the instant your problem is shaped like "these things depend on those things, give me a valid order." Build systems, package managers, task schedulers, course planners, and formula-recalculation engines all reduce to it. It also doubles as a cycle detector, which is often the point: a build system runs a topological sort partly to order compilation and partly to refuse a circular dependency with a clear error. And Kahn's frontier of "ready" nodes is naturally parallel — everything at in-degree zero can run at once — which is why graphlib exposes a mode that hands out batches of ready tasks to worker threads.

Where it doesn't apply is any graph with cycles, by definition — if tasks mutually depend, there is no valid order and the algorithm correctly reports failure rather than inventing one. It also gives you a valid order, not a best one: if you want the order that finishes a project soonest given task durations and parallelism, that's critical-path scheduling, a weighted problem built on top of the topological order, not the sort itself. And it needs the whole dependency graph up front; it isn't an online algorithm that accepts tasks one at a time.

The data, or the inputs

The face-off runs on random DAGs of nine tasks with a growing number of dependency edges, and for each it samples twenty thousand random orderings to measure what fraction happen to be valid — the odds of solving the problem by guessing. The correctness check confirms both our algorithms and graphlib produce orders that respect every edge, on hundreds of random DAGs, and that all three report failure on graphs with a planted cycle. The animation runs Kahn's algorithm on a small build-style DAG so you can watch the in-degrees fall and the ready frontier advance.

Build it, one function at a time

Kahn's algorithm — peel off in-degree-zero nodes, freeing their dependents:

def topo_sort_kahn(adj, n):
    """Kahn's algorithm (1962). Count each node's in-degree (how many prerequisites it has).
    Anything with in-degree 0 is ready to go — put it in a queue. Repeatedly take a ready
    node, append it to the order, and 'remove' it by decrementing its neighbors' in-degrees;
    any neighbor that drops to 0 just became ready. O(V+E). If we place fewer than n nodes,
    the leftovers sit in a cycle and NO valid order exists — we return None."""
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    ready = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # u is placed → one fewer prerequisite for v
            if indeg[v] == 0:
                ready.append(v)
    return order if len(order) == n else None   # short order ⇒ a cycle blocked the rest

The DFS version — reverse of finish-order, cycle-aware:

def topo_sort_dfs(adj, n):
    """The DFS route. A node belongs *after* everything reachable from it, so if we append
    each node to a list the moment DFS FINISHES it (all its descendants done) and then
    reverse the list, we get a topological order. The three-color scheme doubles as a cycle
    check: an edge to a gray (still-open) node is a back edge, so no order exists."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    finished = []
    ok = True

    def visit(u):
        nonlocal ok
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge → cycle → no topological order
                ok = False
            elif color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        finished.append(u)                  # record in finish-order

    for u in range(n):
        if color[u] == WHITE:
            visit(u)
    return finished[::-1] if ok else None   # reverse finish-order = topological order

And the property both guarantee, which a random order almost never has:

def is_valid_topo_order(adj, n, order):
    """An order is a valid topological sort iff it lists all n nodes and every edge u → v has
    u before v. This is the property both algorithms guarantee and a random shuffle almost
    never has."""
    if order is None or len(order) != n or set(order) != set(range(n)):
        return False
    pos = [0] * n
    for i, u in enumerate(order):
        pos[u] = i
    return all(pos[u] < pos[v] for u in range(n) for v in adj[u])

Watch it work

Here's Kahn's algorithm on a small build graph. Green nodes are ready — in-degree zero, all prerequisites met; orange is the node being placed this step; green-checked (dark green) nodes are already placed and crossed off; dark nodes are still blocked, and their label shows their remaining in-degree. Watch the wave of readiness advance left to right: nodes 0 and 1 start ready (nothing points at them); placing them drops the in-degrees of 2 and 3; and the frontier of "ready" tasks sweeps through the graph until everything is ordered. This is the BFS frontier from two chapters ago, now gated by prerequisites instead of distance:

The complete code

Both algorithms plus the validity check on the from-scratch side; the standard-library graphlib.TopologicalSorter on the other. Flip between them — the library version is what you'd actually ship, and it's the same DFS-finish-order algorithm with a scheduling API on top.

"""Topological sort — order the nodes of a directed acyclic graph (DAG) so that every
edge points forward: if there's an edge u → v ("u must come before v"), then u appears
before v in the order. It's the algorithm behind every "what must happen before what"
question: build systems, task schedulers, course prerequisites, spreadsheet recompute.

There are two classic algorithms, and they come straight from the two traversals of the
last two chapters:

  - Kahn's algorithm is BFS-flavored: repeatedly remove a node that has no remaining
    prerequisites (in-degree 0), which frees its dependents.
  - The DFS algorithm is depth-first-flavored: a node's correct position is *after* all
    the nodes it points to, so the reverse of DFS finish-order is a topological order.

Both run in O(V+E). Both also detect the one case where no order exists — a cycle, where
some nodes mutually depend on each other and nothing can go first.
"""
from collections import deque


# region: kahn
def topo_sort_kahn(adj, n):
    """Kahn's algorithm (1962). Count each node's in-degree (how many prerequisites it has).
    Anything with in-degree 0 is ready to go — put it in a queue. Repeatedly take a ready
    node, append it to the order, and 'remove' it by decrementing its neighbors' in-degrees;
    any neighbor that drops to 0 just became ready. O(V+E). If we place fewer than n nodes,
    the leftovers sit in a cycle and NO valid order exists — we return None."""
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    ready = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # u is placed → one fewer prerequisite for v
            if indeg[v] == 0:
                ready.append(v)
    return order if len(order) == n else None   # short order ⇒ a cycle blocked the rest
# endregion


# region: dfs_topo
def topo_sort_dfs(adj, n):
    """The DFS route. A node belongs *after* everything reachable from it, so if we append
    each node to a list the moment DFS FINISHES it (all its descendants done) and then
    reverse the list, we get a topological order. The three-color scheme doubles as a cycle
    check: an edge to a gray (still-open) node is a back edge, so no order exists."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    finished = []
    ok = True

    def visit(u):
        nonlocal ok
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge → cycle → no topological order
                ok = False
            elif color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        finished.append(u)                  # record in finish-order

    for u in range(n):
        if color[u] == WHITE:
            visit(u)
    return finished[::-1] if ok else None   # reverse finish-order = topological order
# endregion


# region: is_valid_order
def is_valid_topo_order(adj, n, order):
    """An order is a valid topological sort iff it lists all n nodes and every edge u → v has
    u before v. This is the property both algorithms guarantee and a random shuffle almost
    never has."""
    if order is None or len(order) != n or set(order) != set(range(n)):
        return False
    pos = [0] * n
    for i, u in enumerate(order):
        pos[u] = i
    return all(pos[u] < pos[v] for u in range(n) for v in adj[u])
# endregion

"""The library counterpart, and this one is real standard library: since Python 3.9,
`graphlib.TopologicalSorter` does exactly this job.

    from graphlib import TopologicalSorter, CycleError
    ts = TopologicalSorter()
    for u in range(n):
        for v in adj[u]:
            ts.add(v, u)          # v depends on u  (u must come before v)
    order = list(ts.static_order())   # raises CycleError if the graph has a cycle

graphlib uses the DFS/finish-order approach under the hood, and it also supports a
parallel-scheduling mode (`prepare()` + `get_ready()` + `done()`) for handing out
batches of ready tasks to worker threads — the same Kahn's-algorithm frontier, exposed
as an API. networkx's `topological_sort` is the third-party equivalent for graph objects.
"""
from graphlib import CycleError, TopologicalSorter


# region: library
def topo_sort_library(adj, n):
    """Standard-library topological sort via graphlib. Returns the order, or None on a cycle
    (graphlib signals a cycle by raising CycleError)."""
    ts = TopologicalSorter()
    for u in range(n):
        ts.add(u)                     # ensure isolated nodes are included
        for v in adj[u]:
            ts.add(v, u)              # v depends on u
    try:
        return list(ts.static_order())
    except CycleError:
        return None
# endregion

Scratch vs library

Unusually for this book, the library counterpart here is the standard library: graphlib shipped with Python 3.9, so topological sort is a batteries-included call. Our from-scratch versions and graphlib all produced valid orders on every test — sometimes different valid orders, because a DAG typically admits many, and that's the subtle lesson. The two algorithms aren't approximations of each other; they're both exact, making different arbitrary choices among tasks that the dependencies leave unordered. So the right correctness test isn't "does it match graphlib" — it's "does every edge point forward," the property in is_valid_topo_order. When a problem has many correct answers, testing for one specific answer is a bug; test for the property that defines correctness. In production you'd reach for graphlib (or networkx for graph objects); building it once yourself is what makes the "why does the order differ?" question have an obvious answer instead of a mysterious one.

Where you'll actually meet it

Topological sort runs under an enormous amount of software. Every build system — make, bazel, cargo, npm, gradle — topologically sorts its dependency graph to decide compile order and to reject circular dependencies. Package managers (apt, pip's resolver, conda) order installation the same way. Spreadsheet engines recompute cells in topological order and flag circular references with it. Task schedulers and workflow engines (Airflow, CI pipelines, make -j) use it to find which jobs can run now and which must wait. Compilers order instruction scheduling and use it in data-flow analysis. Course-planning tools order prerequisites with it. Anywhere the words "depends on," "must come before," or "prerequisite" appear, a topological sort is doing the work.

Takeaways

Topological sort flattens a directed acyclic graph of dependencies into a linear order where every edge points forward, in $O(V+E)$. It comes in two flavors that are the last two chapters reused: Kahn's algorithm peels off nodes with no remaining prerequisites (a BFS frontier gated by in-degree), and the DFS version reverses finish-order. Both detect the one failure case — a cycle, where no order exists — and both find a valid order instantly where guessing essentially never would. The order isn't unique, so correctness means "every edge points forward," not "matches this exact sequence."

From here the graph tier turns to weighted problems. The next chapters — Dijkstra, Bellman-Ford, and the rest — ask not just "what order" or "is it reachable" but "what's the cheapest way," attaching costs to edges. The traversals so far treated every edge as one equal step; weights break that assumption, and BFS's shortest-path guarantee with it, which is exactly the gap Dijkstra's algorithm fills next.