Topological Sort

Ordering things that depend on each other

Some tasks must happen before others. To take a course you must first take its prerequisites; to build a source file you must first build the modules it imports; to run a cell in a spreadsheet you must first compute the cells it references. Even getting dressed has this shape: socks go on before shoes, a shirt before a jacket, and no rule stops you from putting your belt on before your shirt — those two just don't constrain each other at all. Model each task as a vertex and each "A must come before B" constraint as a directed edge A→B. A topological sort (or topological ordering) is a linear ordering of all the vertices such that for every edge A→B, A appears before B. Produce such an ordering and you have a valid schedule: do the tasks in that order and no task ever runs before something it depends on.

When is it even possible? Only for DAGs

A topological order does not always exist. Suppose A→B, B→C, and C→A. Any valid order must put A before B (edge A→B), B before C (edge B→C), and C before A (edge C→A) — so A must come before C which must come before A, a contradiction. No ordering can satisfy all three. The obstruction is exactly the cycle A→B→C→A: a cycle is a set of tasks each waiting on the next, forming a loop with no possible starting point — a rule that said "belt before pants, pants before shirt, shirt before belt" would leave you unable to put on ANY of the three first, no matter where you started.

So a topological sort is well-defined if and only if the graph is a DAG — a directed acyclic graph. "Directed" because the constraints have a direction (before/after); "acyclic" because any cycle makes ordering impossible, as just shown. Every topological-sort algorithm therefore does double duty: it produces an order when one exists, and it detects the presence of a cycle when one doesn't. Both algorithms below make this explicit.

Kahn's algorithm — BFS by in-degree

A vertex with in-degree zero — no incoming edges — depends on nothing, so it is safe to place first: your socks, your underwear, anything with no prerequisite of its own. Kahn's algorithm builds the order by repeatedly doing exactly that:

1. Compute each vertex's in-degree (number of incoming edges).
2. Put all in-degree-zero vertices in a queue — these have no unmet dependencies.
3. Repeatedly remove a vertex from the queue, append it to the output, and "delete" it by decrementing the in-degree of each vertex it points to. Any neighbor whose in-degree hits zero has now had all its dependencies placed, so enqueue it — putting your socks on is exactly what clears shoes' one dependency and makes shoes available to put on next.
4. When the queue empties, if every vertex made it into the output, that's a valid topological order. If some vertices never reached in-degree zero, they are caught in a cycle — no valid order exists.

from collections import deque

def topo_sort_kahn(num_vertices: int,
                   adj: list[list[int]]) -> list[int] | None:
    indegree = [0] * num_vertices
    for u in range(num_vertices):
        for v in adj[u]:
            indegree[v] += 1                # count incoming edges

    queue = deque(u for u in range(num_vertices) if indegree[u] == 0)
    order: list[int] = []
    while queue:
        u = queue.popleft()
        order.append(u)                     # u has no remaining dependencies
        for v in adj[u]:
            indegree[v] -= 1                # remove u's edge into v
            if indegree[v] == 0:            # v's last dependency just cleared
                queue.append(v)

    # If a cycle exists, its vertices never hit in-degree 0 and are missing.
    return order if len(order) == num_vertices else None

Why the cycle check works. Every vertex in the output was emitted only after its in-degree reached zero, i.e. after every one of its predecessors was already emitted — so the "A before B" property holds by construction. And a vertex on a cycle can never reach in-degree zero: some predecessor on the cycle is also stuck waiting, so neither is ever emitted. If the output count is short of V, exactly the cycle-trapped vertices are missing — that is the cycle detection, for free.

Complexity. Computing in-degrees scans every edge once: O(V + E). Each vertex is enqueued and dequeued at most once (it hits in-degree zero once), and each edge is used exactly once for its decrement. Total O(V + E) time, O(V) space for the in-degree array and queue.

DFS-based topological sort — postorder, reversed

The second algorithm uses depth-first search and a fact about when DFS finishes a vertex. Run DFS; when a vertex's recursive call is about to return — after the loop over all its neighbors has completed — append it to a list. This is the postorder finish order. Then reverse that list. The reversed postorder is a valid topological order.

def topo_sort_dfs(num_vertices: int,
                  adj: list[list[int]]) -> list[int] | None:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_vertices
    postorder: list[int] = []
    has_cycle = False

    def visit(u: int) -> None:
        nonlocal has_cycle
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge into active path → cycle
                has_cycle = True
            elif color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        postorder.append(u)                 # u finishes AFTER all descendants

    for start in range(num_vertices):
        if color[start] == WHITE:
            visit(start)

    if has_cycle:
        return None
    postorder.reverse()                     # dependencies now come first
    return postorder

Why reversed postorder is correct — a proof, not an assertion

The claim to prove: for every edge u→v, u appears before v in the reversed postorder. Equivalently, u appears after v in the raw postorder — i.e. u finishes its DFS call later than v does.

Take any edge u→v and look at the moment DFS processes that edge, while inside visit(u). When visit(u) reaches v in u's neighbor loop, v is in one of two states (assuming no cycle, which we've separately detected):

• v is white (unvisited). Then visit(u) calls visit(v) right now. That recursive call runs to completion — fully finishing v and appending it to postorder — before control returns to u's loop, and u only finishes after its loop ends. So v is appended before u. ✓
• v is black (already finished). Then v was appended to postorder at some earlier time, and u has not finished yet (we're still inside its loop). So v is appended before u. ✓
• v is gray (on the current stack) would mean v is an ancestor of u and u→v closes a cycle. That case is exactly what the gray-edge check flags, and we return "no order" — so it can't occur in a successful run.

In both possible cases, v is appended to postorder before u. Since that holds for every edge u→v, every vertex finishes after all vertices it points to (all its descendants in the dependency sense). Reversing the postorder therefore places every u before every v it has an edge to — which is precisely the definition of a topological order. The key structural fact powering this: a vertex's DFS call cannot finish until all vertices reachable from it have finished, because those calls are nested inside it. Reversing "finish order" turns "finishes last" into "comes first," and dependencies (which finish later) land ahead of their dependents.

Which to reach for

Both are O(V + E); the choice is stylistic and situational. Kahn's is iterative (no recursion-depth limit to worry about on huge graphs) and its queue naturally produces a "process things as their dependencies clear" order that's easy to reason about — and it hands you the in-degree-zero frontier, which some problems want directly. The DFS version is a tiny addition to a traversal you already know and is convenient when you're already doing DFS for other reasons. The two related problems in this module lean on Kahn's: Course Schedule (does any valid order exist — i.e. is the graph acyclic) and Course Schedule II (return an actual order).