A topological sort produces a linear ordering of the nodes in a directed acyclic graph (DAG) such that every edge points from an earlier node to a later one. In plain terms, if task A must happen before task B, A appears before B in the output. A valid ordering exists only when the graph has no cycle, which makes topological sort a natural way to detect cycles too.
When to use it#
Use this pattern whenever a problem involves ordering items under “must come before” constraints: course prerequisites, build dependencies, task scheduling, or resolving symbol references. The signals are a directed graph plus a question about a valid sequence, or a question about whether the constraints are even satisfiable.
Worked example#
Kahn’s algorithm builds the order by repeatedly removing nodes with no remaining incoming edges:
1from collections import deque
2
3def topo_sort(num_nodes, edges):
4 graph = [[] for _ in range(num_nodes)]
5 indegree = [0] * num_nodes
6 for src, dst in edges:
7 graph[src].append(dst)
8 indegree[dst] += 1
9
10 queue = deque(n for n in range(num_nodes) if indegree[n] == 0)
11 order = []
12 while queue:
13 node = queue.popleft()
14 order.append(node)
15 for neighbor in graph[node]:
16 indegree[neighbor] -= 1
17 if indegree[neighbor] == 0:
18 queue.append(neighbor)
19
20 return order if len(order) == num_nodes else [] # empty means a cycle exists
If the final order is shorter than the node count, some nodes never reached indegree zero, which proves a cycle. A depth-first version using post-order traversal works too.
Complexity#
Time is O(V + E), where V is the number of nodes and E the number of edges, since each node and edge is processed once. Space is O(V + E) for the adjacency list and the queue.
Practice problems#
- Course Schedule I and II
- Alien Dictionary
- Minimum Height Trees
- Sequence Reconstruction
- Parallel Courses
- Sort Items by Groups Respecting Dependencies
For undirected connectivity and cycle detection instead of directed ordering, compare with Union-Find. Return to the pattern hub.