Topological Sort

#How does it work?

A topological sort orders the nodes of a directed acyclic graph (DAG) so that for every arrow u → v, u comes before v. It is how you resolve "do this first, then that" dependencies.

Kahn's algorithm (1962) starts with the nodes whose in-degree (number of incoming edges) is 0, i.e. those with no prerequisites left. When a node is output its outgoing arrows count as done and each target's in-degree drops by one; a node that reaches 0 joins the queue.

If the graph has a cycle, the in-degree of the nodes on it never reaches 0. The queue empties early and fewer than V nodes are ordered: Kahn's algorithm doubles as a cycle detector.

A DAG can have more than one valid topological order. DFS is the alternative: prepending each node once all its branches are done also yields a topological order.

#Try it yourself

#Step by step

1. 01Compute the in-degree of every node.
2. 02Put every node with in-degree 0 in the queue.
3. 03Take a node u from the queue and append it to the order; for each arrow out of u, lower the target's in-degree by 1 and queue it when it hits 0.
4. 04When the queue is empty, fewer than V ordered nodes means the graph has a cycle.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from collections import deque

# u -> v means "u before v", e.g. course prerequisites.
EDGES = [(1, 2), (1, 3), (3, 2), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]


def topo_sort(n: int, edges) -> list:
    """Kahn's algorithm. Returns the order, or an empty list if there is a cycle."""
    out = {v: [] for v in range(1, n + 1)}
    indegree = {v: 0 for v in range(1, n + 1)}
    for u, v in edges:
        out[u].append(v)
        indegree[v] += 1
    queue = deque(v for v in range(1, n + 1) if indegree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in sorted(out[u]):
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else []


print(" ".join(map(str, topo_sort(7, EDGES))))
print("cycle" if not topo_sort(7, EDGES + [(7, 1)]) else "no cycle")  # 7 -> 1 closes a loop

#Complexity

Each node enters the queue once and each arrow is processed once, so the whole thing is linear. An order only exists for DAGs; it isn't defined for undirected graphs or directed graphs with cycles.

#When to use it?

Build systems (make, npm/yarn dependencies), task scheduling, planning course prerequisites, recalculating spreadsheet cells, ordering database migrations and package managers all use topological sorting.

#Practice

Log in to answer questions and save your progress.