Topological sort explained: how it works, code and complexity

What problem topological sort solves

Many real tasks have prerequisites: a course requires earlier courses, a source file must be compiled after the files it imports, a package must be installed after its dependencies, a spreadsheet cell must be computed after the cells it references. Draw each task as a node and each "must come before" rule as a directed edge. A topological order is any sequence of the tasks that respects every edge.

An order exists if and only if the graph has no directed cycle. If A needs B and B needs A, no valid order exists, and a good topological sort reports that instead of looping forever. A DAG usually has many valid orders; the algorithms return one of them.

The idea in plain words

Kahn's algorithm (published by Arthur Kahn in 1962) works from the front:

1. Count the incoming edges (the in-degree) of every node.
2. Put every node with in-degree 0 into a queue: these tasks have no unmet prerequisites.
3. Take a node from the queue and append it to the result. For each of its outgoing edges, lower the target's in-degree by 1; if it reaches 0, add the target to the queue.
4. When the queue is empty, if the result contains every node, it is a topological order. Otherwise the remaining nodes are part of a cycle.

The DFS method works from the back: a node is finished only after everything it points to is finished, so listing nodes in reverse finishing order puts each node before all of its successors.

Worked example, step by step

Getting dressed: underwear → pants, pants → shoes, socks → shoes, pants → belt, shirt → belt, shirt → tie, tie → jacket, belt → jacket. Kahn's algorithm, taking queued nodes in first-in, first-out order:

Final order: underwear, socks, shirt, pants, tie, shoes, belt, jacket. All 8 nodes are placed, so there is no cycle.

Python implementation

Kahn's algorithm with a deque:

from collections import deque
def topo_sort(graph):
    """graph: dict node -> list of nodes that must come after it."""
    indegree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            indegree[m] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for m in graph[n]:
            indegree[m] -= 1
            if indegree[m] == 0:
                queue.append(m)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order
dress = {
    "underwear": ["pants"], "socks": ["shoes"], "shirt": ["belt", "tie"],
    "pants": ["shoes", "belt"], "tie": ["jacket"], "belt": ["jacket"],
    "shoes": [], "jacket": [],
}
print(topo_sort(dress))
# ['underwear', 'socks', 'shirt', 'pants', 'tie', 'shoes', 'belt', 'jacket']

The DFS version appends a node after all its successors are done, then reverses the list:

def topo_sort_dfs(graph):
    order, state = [], {}             # state: 1 = in progress, 2 = done
    def visit(n):
        if state.get(n) == 1:
            raise ValueError("graph has a cycle")
        if state.get(n) == 2:
            return
        state[n] = 1
        for m in graph[n]:
            visit(m)
        state[n] = 2
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]
print(topo_sort_dfs(dress))
# ['shirt', 'tie', 'socks', 'underwear', 'pants', 'belt', 'jacket', 'shoes']

Both outputs are valid. Since Python 3.9, the standard library also has graphlib.TopologicalSorter. Note that it takes a mapping from each node to its predecessors, the opposite direction from the dictionaries above:

from graphlib import TopologicalSorter
ts = TopologicalSorter({"b": {"a"}, "c": {"a", "b"}})   # node: its prerequisites
print(list(ts.static_order()))  # ['a', 'b', 'c']

Time and space complexity

Variants and common mistakes

• Smallest order first: replace the queue with a min-heap (heapq) to always pick the smallest available node. This gives the lexicographically smallest order in O((V + E) log V).
• Parallel scheduling: process Kahn's algorithm in rounds, taking all in-degree-0 nodes at once. Each round is a batch of tasks that can run at the same time; the number of rounds is the length of the longest dependency chain. graphlib.TopologicalSorter supports this with get_ready() and done().
• Longest or shortest path in a DAG: relax edges in topological order to get the answer in O(V + E), even with negative weights.
• Counting distinct orders is a much harder problem; do not try to list them all for large graphs.

The recursive DFS version has the same recursion limit issue as any recursive DFS in Python: for chains of thousands of nodes, use Kahn's algorithm.

When to use it and real-world uses

• Build tools such as Make order targets by their dependencies, and package managers order installs by dependency graphs.
• Spreadsheets recalculate cells in dependency order and report circular references.
• Task schedulers and workflow engines, for example DAG-based data pipelines, run tasks in topological order.
• Compilers order declarations and evaluate expression graphs; databases order foreign-key creation or deletion.
• Interview problems: course schedule I and II, alien dictionary (letter order from sorted words), parallel courses, minimum height of a build plan.