Skip to main content

Topological Sort

Overview​

A topological sort orders the vertices of a directed acyclic graph so that every edge points forward — if A must happen before B, A appears earlier. It is the algorithm behind build systems, package managers, task schedulers and spreadsheet recalculation, all of which face the same question: given these dependencies, what order can I do the work in?

A directed acyclic graph drawn so that every arrow points from left to right, with no arrow doubling back
The same DAG laid out in topological order. Every arrow points forward — that layout existing at all is exactly what acyclicity guarantees. Wikimedia Commons, CC0

Core Concepts​

TermMeaning
DAGDirected acyclic graph — the precondition. A cycle makes ordering impossible
In-degreeNumber of incoming edges; a vertex with in-degree 0 has no unmet prerequisites
Valid orderingsUsually many. The algorithms find a valid order, not the order
A cycle is not a failure mode — it is the answer

If the graph has a cycle, no valid ordering exists, and both algorithms below detect it. That detection is often the more useful output: "circular dependency between A, B and C" is precisely what a package manager or build tool needs to report.

Architecture / Mechanism​

Kahn's algorithm (BFS-based)​

Repeatedly take a vertex with no remaining prerequisites, output it, and remove its edges:

from collections import deque

def topological_sort(graph):
    """graph: {node: [dependents...]}, an edge u -> v meaning u must come before v."""
    in_degree = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque(v for v, d in in_degree.items() if d == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1           # u is done; one prerequisite satisfied
            if in_degree[v] == 0:
                queue.append(v)

    if len(order) != len(graph):        # some vertices never reached in-degree 0
        raise ValueError("graph contains a cycle")
    return order

The final length check is the cycle detection: vertices inside a cycle always have at least one unsatisfied prerequisite, so they never enter the queue.

DFS-based​

Run depth-first search and prepend each vertex as it finishes. A vertex finishes only after everything it depends on has, so the reversed finishing order is a topological order:

def topological_sort_dfs(graph):
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {v: WHITE for v in graph}
    order = []

    def visit(u):
        if colour[u] == GREY:
            raise ValueError("graph contains a cycle")
        if colour[u] == BLACK:
            return
        colour[u] = GREY
        for v in graph[u]:
            visit(v)
        colour[u] = BLACK
        order.append(u)                 # post-order: appended after all descendants

    for v in graph:
        visit(v)
    return order[::-1]                  # reverse the finishing order
Kahn'sDFS-based
TraversalBreadth-firstDepth-first
Cycle detectionOutput shorter than vertex countA GREY vertex revisited
RecursionNoneYes — stack depth O(V)
Ordering controlSwap the queue for a heap to get a deterministic or prioritised orderFixed by the traversal
Natural extensionLevel-by-level parallel scheduling—

Kahn's is usually preferable: it is iterative, its cycle detection is a single comparison, and it extends naturally to the parallel case below.

Practical Usage​

# Everything at the same "level" has no dependencies between its members,
# so each level can be executed in parallel.
def parallel_batches(graph):
    in_degree = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    ready = [v for v, d in in_degree.items() if d == 0]
    batches = []
    while ready:
        batches.append(ready)                # this whole batch can run concurrently
        nxt = []
        for u in ready:
            for v in graph[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    nxt.append(v)
        ready = nxt
    return batches

This is what make -j and modern build systems do: compute the dependency levels, then run each level's tasks in parallel. The number of batches is the graph's critical path length, and it is a hard floor on build time no matter how many cores you add — the same argument as Amdahl's law.

DomainVerticesEdge means
Build systems (make, Bazel)Targets"must be built before"
Package managers (apt, pip, cargo)Packages"depends on"
SpreadsheetsCells"is referenced by"
Course planningCourses"is a prerequisite for"
Task runners, CI pipelinesJobs"must complete before"
CompilersInstructionsData dependency — used for scheduling

Edge Cases & Pitfalls​

  • Edge direction is the most common bug. Decide whether your map means "depends on" or "is depended on by" — reversing it produces a perfectly plausible, exactly backwards order.
  • Isolated vertices belong in the output. A package with no dependencies still needs installing; make sure it is initialised in in_degree.
  • Vertices appearing only as targets may be missing from graph's keys, causing a KeyError. Build the vertex set from both endpoints of every edge.
  • The result is not unique. Tests asserting one specific order will break when the iteration order changes. Assert the constraints — that each vertex precedes its dependents — or use a heap for a deterministic order.
  • DFS recursion depth is O(V); use Kahn's for large graphs.

References​

  • Kahn, A.B. (1962), "Topological sorting of large networks", Communications of the ACM — the original.
  • Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, §22.4 — the DFS-based version, with the proof that reverse finishing order is a valid ordering.

Books & Videos​