Topological Sort

What topological order means

Given a directed graph, a topological order is a linear arrangement of its nodes such that for every edge u → v, u appears before v in the order. Equivalently: the nodes are listed in an order that respects all dependencies.

The graph must be a DAG, a directed acyclic graph. If a cycle exists, no topological order is possible (the cycle's nodes all depend on each other). Algorithms that compute topological order also report cycles as a by-product.

Kahn's algorithm. BFS-flavoured

Start with all nodes whose in-degree is zero (no incoming dependencies). Process them in any order, removing their outgoing edges. Whenever a node's in-degree drops to zero, add it to the ready queue. Continue until the queue is empty.

from collections import deque

def topo_sort_kahn(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    q = deque([u for u, d in indeg.items() if d == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) != len(graph):
        raise ValueError("cycle detected")
    return order

O(V + E) time, O(V) memory. The cycle check is implicit: if any node has in-degree > 0 at the end, it's part of a cycle (or downstream of one), total nodes processed will be less than V.

Kahn's is the natural choice when you want the topological order to be lexicographic among ties. Replace the FIFO queue with a min-heap; you get the lexicographically smallest order. O((V + E) log V).

DFS post-order

Run DFS. Record nodes in post-order (when DFS finishes them, not when it discovers them). Reverse the result, that's a topological order.

def topo_sort_dfs(graph):
    visited = set()
    order = []

    def dfs(u):
        if u in visited: return
        visited.add(u)
        for v in graph[u]:
            dfs(v)
        order.append(u)                                 # post-order

    for u in graph:
        dfs(u)
    return order[::-1]                                  # reverse

Why this works: a node is finished only after all its descendants are finished. So in the finish-order, descendants come before ancestors. Reversing puts ancestors before descendants, which is topological order.

Cycle detection requires more care here. Use the three-colour DFS (see the BFS vs DFS deep-dive) to detect back edges during the traversal. If any back edge exists, the graph has a cycle and no topological order is possible.

Choosing between the two

A worked example

Graph: A → C, B → C, B → D, C → E, D → E, F → A.

In-degrees:
F: 0    A: 1 (from F)    B: 0
C: 2 (from A, B)         D: 1 (from B)
E: 2 (from C, D)

Kahn's run:
  queue: [F, B]            order: []
  pop F: order [F]; decrement A's in-deg → 0; queue: [B, A]
  pop B: order [F, B]; decrement C's → 1, D's → 0; queue: [A, D]
  pop A: order [F, B, A]; decrement C's → 0; queue: [D, C]
  pop D: order [F, B, A, D]; decrement E's → 1; queue: [C]
  pop C: order [F, B, A, D, C]; decrement E's → 0; queue: [E]
  pop E: order [F, B, A, D, C, E]; done.

Verify: every edge goes left-to-right in the order. ✓

Applications

Course schedule

"You must take courses in some order; each course has prerequisites. Can you finish all courses? If yes, in what order?" Build the graph; topological sort. If cycle detected, no valid order. See the Course Schedule walkthrough.

Build systems (Make, Bazel)

Each target depends on other targets being built first. Topological sort gives the order in which to compile. Modern build systems also parallelise, sort and then schedule independent nodes concurrently.

Package managers

"Install package P, which depends on Q and R, which depend on S." Topological sort gives the install order. Cycles indicate version conflicts; the package manager either picks one or reports an error.

Spreadsheet recalculation

Cells form a DAG of formula references. When a cell changes, recalculate downstream cells in topological order. Cycles in formulas (A = B + 1, B = A + 1) are circular references, most spreadsheets refuse to evaluate them.

ML pipeline scheduling

Apache Airflow, Prefect, Kubeflow, all schedule "DAGs of tasks." Topological sort gives execution order; cycle detection at DAG-definition time prevents impossible workflows.

Counting all topological orders

A DAG can have many valid topological orders. The count is a hard combinatorial problem in general (#P-complete). For small DAGs you can enumerate via DFS-with-backtracking; for large ones, sampling or random topological order is the practical approach.

Where beginners go wrong

• Running topological sort on a non-DAG. The algorithm produces a partial order; the remaining unprocessed nodes are the cycle's residue. Always check whether all nodes appear in the output.
• Confusing edge direction. If you build the graph "edge u → v means u must come before v", topo sort gives you u before v. Reversing the convention gives reverse-topo order, and silently wrong answers.
• Using DFS pre-order instead of post-order. Pre-order doesn't give topological order. Post-order (then reverse) does.
• Forgetting in-degree maintenance. In Kahn's, every edge removal must decrement the destination's in-degree, then check whether the destination is ready. Skip one and the queue runs dry too early.
• Trying to detect cycles before computing the order. One pass of either algorithm does both. Two passes are wasted work.

What to read next

The BFS vs DFS Decision Guide covers the underlying graph-traversal trade-off. The Dijkstra Invariant piece covers the related problem of shortest paths on a DAG (which uses topological order). The Graphs module sits above both.