Topological Sort — Worked Example

What It Is

A topological sort takes a directed acyclic graph (a DAG — directed edges, no cycles) and produces a linear ordering of its vertices such that for every edge u → v, u comes before v in the ordering. It only exists to answer one question: "given a bunch of 'this must happen before that' constraints, is there a valid order to do everything in, and if so what is it?"

Two things worth internalizing up front: a topological order is not unique — most DAGs have many valid orderings, any one of them is a correct answer — and a topological order only exists at all if the graph has no cycle. If A must come before B, and B must come before A, there is no valid order, full stop.

The Example: Getting Dressed

You can't put your shoes on before your socks, or your jacket on before your shirt. Encode those real constraints as a graph — nine items of clothing (plus a watch, which depends on nothing) and nine "must happen before" edges:

Any valid answer must respect every one of those nine edges simultaneously. There's no single "correct" order — socks and undershorts could go on in either relative order, for instance — but the two algorithms below each produce one specific valid order.

Kahn's Algorithm (BFS, In-Degree Based)

The idea: an item with zero unmet prerequisites (in-degree 0) is always safe to put on right now. Put it on, then "remove" it from the graph — which means decrementing the in-degree of everything it pointed to, since one of their prerequisites is now satisfied. Repeat. Anything whose in-degree just hit 0 becomes safe to process next.

from collections import deque

def kahn_topological_sort(nodes, edges):
    graph = {n: [] for n in nodes}
    in_degree = {n: 0 for n in nodes}
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    # every item with zero unmet prerequisites is safe to start with
    queue = deque(n for n in nodes if in_degree[n] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            # this neighbor's last prerequisite was just satisfied
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # fewer nodes processed than exist means a cycle blocked the rest
    if len(order) != len(nodes):
        raise ValueError("graph has a cycle -- no valid order exists")
    return order

Full Trace

Initial in-degrees: socks=0, undershorts=0, pants=1, shoes=3, belt=2, shirt=0, tie=1, jacket=2, watch=0. Initial queue (everything already at 0): [socks, undershorts, shirt, watch].

Final order: socks, undershorts, shirt, watch, pants, tie, shoes, belt, jacket — 9 items, matching the 9 nodes, so no cycle. Every one of the nine edges checks out (e.g. pants at position 4 comes before shoes at position 6 and belt at position 7, exactly as required).

Key Functions & Tricks

• collections.deque — O(1) pop from the front, unlike list.pop(0) which is O(n); matters here since the queue is popped once per node
• {n: [] for n in nodes} / {n: 0 for n in nodes} — dict comprehensions to pre-initialize every node's adjacency list and in-degree counter before any edges are added
• deque(n for n in nodes if in_degree[n] == 0) — builds the initial frontier directly from a generator expression, no separate loop needed
• if in_degree[neighbor] == 0: — a neighbor only becomes eligible the exact moment its last prerequisite clears, which is what guarantees every edge is respected
• len(order) != len(nodes) — the cycle-detection check; nodes stuck in a cycle never reach in-degree 0, so they're silently left out of order

Alternative: DFS-Based Topological Sort

A second, equally standard approach: run a DFS from every unvisited node, and every time you finish exploring a node completely (all its descendants are done), push it onto the front of the result — or equivalently, append it to a list and reverse the whole list at the end.

def dfs_topological_sort(nodes, edges):
    graph = {n: [] for n in nodes}
    for u, v in edges:
        graph[u].append(v)

    visited = set()
    order = []

    def visit(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visit(neighbor)
        # postorder: a node is only appended after ALL its descendants are done
        order.append(node)

    for node in nodes:
        if node not in visited:
            visit(node)

    order.reverse()
    return order

Why reversing works: if visit(u) recursively calls visit(v) for an edge u → v, then v finishes (gets appended) strictly before u does — u is still waiting on the call stack. So in the raw order list, every edge's target appears before its source; reversing the whole list flips that into "every edge's source appears before its target," which is exactly the topological property we want.

Kahn's and DFS-based sort can both produce a valid order for the same graph, and for a graph with more than one valid order, they won't necessarily produce the same one — both are correct, since topological order isn't unique to begin with.

Detecting a Cycle

Suppose someone mistakenly adds a constraint that shoes must go on before undershorts — shoes → undershorts — on top of the existing undershorts → shoes edge. That's a direct two-node cycle: undershorts needs shoes, and shoes needs undershorts. Nothing in that cycle can ever be "first." Running Kahn's algorithm on this broken graph:

The queue empties after only 4 nodes (socks, shirt, watch, tie) out of 9. undershorts, pants, shoes, belt, and jacket are all stuck at in-degree ≥ 1 forever — each is waiting, directly or transitively, on the undershorts↔shoes cycle to resolve, which it never does. The len(order) != len(nodes) check (4 ≠ 9) is exactly what catches this, which is why every topological-sort solution needs that check — without it, the function would silently return a partial, incomplete order instead of raising an error.

How to Recognize This Pattern, and Common Pitfalls

Where This Shows Up in This Set

Problems #5 (topological ordering directly), #20 (the cycle-detection-only variant — "can all stages complete"), and #35 (deriving an ordering from partial/observed constraints, the hardest of the three) all use this pattern in a Fin-pipeline framing. See the Pattern Catalog for how this fits alongside the other ~19 patterns in this set.