Topological Sort

TL;DR

Topological sort linearises a directed acyclic graph (DAG) into a sequence where every edge u → v points forward — u always appears before v. That’s exactly what you need when nodes have prerequisites: courses, build targets, ETL stages, package installs.

Two algorithms, both O(V + E). Kahn’s algorithm is BFS-driven: track in-degree per node, emit any node with in-degree 0, decrement its children, repeat. DFS post-order runs a recursion that emits a node only after all its descendants are emitted, then reverses the result. Pick Kahn’s when you want the order built incrementally (and it’s easier to parallelise); pick DFS when you’re already walking the graph for other reasons.

Both algorithms double as cycle detection. If Kahn’s emits fewer nodes than the graph contains, the leftover nodes form a cycle. If DFS revisits a node currently on the recursion stack (the “gray” state), you’ve closed a cycle. A DAG with a cycle has no valid topo order — that’s not a bug in your algorithm, it’s a property of the input.

When to reach for it

Signals that topological sort is the right tool:

• Prerequisite ordering. “Course a must be taken before course b” or “task a must finish before task b.” If you can phrase the constraint as a directed edge, you want topo sort.
• Build / dependency graphs. Make targets, Bazel actions, npm packages, Terraform resources — anything where one node can’t be processed until its inputs are ready.
• Pipeline DAG resolution. Airflow, Prefect, Dagster, Spark stage DAGs — the scheduler walks a topo order to decide what’s runnable next.
• “Is this a DAG?” / cycle detection. Even if you don’t need the order, running topo sort tells you whether a cycle exists.

Signals that it’s not topo sort: edges are undirected (use union-find or plain BFS), edges carry weights that represent duration and you want the longest path (that’s critical-path / longest-path-in-DAG, related but different), or you need all valid orderings rather than any one (that’s backtracking over topo orders, exponential).

Flavor 1 — Kahn’s algorithm (BFS)

Compute in-degree for every node. Seed a queue with all in-degree-0 nodes. Pop, emit, decrement children’s in-degrees, enqueue any child that just hit 0. If the emitted list has fewer than n entries, there’s a cycle.

from collections import deque, defaultdict

def topo_kahn(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    graph = defaultdict(list)
    in_deg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_deg[v] += 1

    queue = deque(i for i in range(n) if in_deg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    return order if len(order) == n else None  # None = cycle

Worked example. Four courses, edges [(0, 1), (0, 2), (1, 3), (2, 3)]. Course 0 unlocks 1 and 2; both unlock 3.

Initial in-degree: [0, 1, 1, 2]. Initial queue: [0].

Length 4 == n, so the order is valid. Note that [0, 2, 1, 3] would also be a valid topo order — Kahn’s resolves ties by queue insertion order, and any tie-breaking rule that pops an in-degree-0 node is correct.

Flavor 2 — DFS post-order

Walk the graph depth-first. A node’s children must finish (be fully emitted) before the node itself is emitted. Reverse the resulting list and you have a topo order. Track three states per node — unseen, on the recursion stack, fully done — to catch back edges (cycles).

def topo_dfs(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []

    def dfs(u: int) -> bool:
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return False              # back edge → cycle
            if color[v] == WHITE and not dfs(v):
                return False
        color[u] = BLACK
        order.append(u)                   # post-order emit
        return True

    for u in range(n):
        if color[u] == WHITE and not dfs(u):
            return None
    return order[::-1]

Trace on the same graph, starting DFS from node 0. Visit 0 (gray), recurse to 1 (gray), recurse to 3 (gray) — 3 has no children, mark black, append. Back to 1, mark black, append. Back to 0, recurse to 2, recurse to 3 (already black, skip), mark 2 black, append. Mark 0 black, append. order = [3, 1, 2, 0]. Reverse: [0, 2, 1, 3] — valid.

Why it works — the invariant

Kahn’s invariant. A node with in-degree 0 has no remaining prerequisites — every edge into it has either never existed or been “removed” by a previous emission. Emitting it cannot violate any ordering constraint, because there’s no u → this left to honor. After emission, decrement each child’s in-degree; the child is now one step closer to being prerequisite-free. The graph shrinks by one node per iteration; if it ever stalls with nodes remaining, those nodes mutually depend on each other — a cycle.

DFS invariant. A node finishes (turns black) only after every descendant reachable from it has finished. So in the post-order list, descendants appear before their ancestor. Reverse the list and ancestors land before descendants — exactly the topo property. The gray state catches the only failure mode: encountering a node currently on the call stack means there’s a path from that node back to itself, i.e. a cycle.

Complexity

• Time: O(V + E). Each node is enqueued/visited once; each edge is inspected once when we walk a node’s adjacency list.
• Space: O(V) for the in-degree array (Kahn’s) or color array (DFS), plus O(V) for the queue / recursion stack and O(V) for the output. The adjacency list itself is O(V + E), but that’s the input representation, not extra space introduced by the algorithm.

Common pitfalls

• Treating an undirected graph as topo-sortable. Topo sort is defined on directed graphs. An undirected edge means “either order is fine,” which trivially makes every node both before and after every other — and any non-trivial undirected graph contains a cycle. Use BFS or union-find instead.
• Building in-degree from the wrong direction. If the edge (a, b) in your input means “a depends on b” (i.e. b must come first), then the directed edge in the graph is b → a, not a → b. Get this backwards and you’ll get a reverse topo order — or, if the graph is asymmetric in shape, an apparent cycle. Always write down which way the arrow points before you start coding.
• Missing isolated nodes. Nodes with no incoming or outgoing edges still belong in the output. Iterate range(n) to seed the queue, not graph.keys() — a node that never appears in any edge won’t have an adjacency list entry in a defaultdict-style graph.
• Returning a partial order on a cyclic graph. If len(order) < n, there’s a cycle and the partial order is meaningless for scheduling — return None (or raise) rather than handing the caller a half-baked list they’ll trust.
• Applying topo sort to weighted scheduling. If edges encode durations and you want the earliest finish time, that’s the critical-path problem (longest path in a DAG). Topo sort gives you the evaluation order; you still need a DP pass over that order to compute finish times. Don’t confuse the two.

Where you see this in production

• Bazel / Buck / Make build graphs. Every build system models targets as a DAG and walks a topo order to decide what to (re)build. Bazel’s scheduler additionally parallelises across same-rank in-degree-0 nodes — that’s Kahn’s algorithm with a thread pool sitting on the queue.
• Airflow and Prefect DAG runners. Both compute a topological order of tasks at parse time, then dispatch tasks to workers as soon as their upstream dependencies finish. The cycle check at DAG-load time is exactly the len(order) != n test from Kahn’s.
• Spark stage scheduling. The DAGScheduler topologically orders stages produced by RDD lineage, submitting a stage only after its shuffle-map parents have completed.
• npm / pnpm install order. Package managers topologically sort the dependency graph so that a package’s postinstall hook runs only after all its dependencies are on disk. A cycle here surfaces as the classic “circular dependency” warning.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• William Fiset — Topological Sort — www.youtube.com