Topological Sort
Motivation
Many real-world processes have prerequisite structure: course requirements, build dependencies, task schedules, spreadsheet recalculations. Each of these can be modelled as a directed acyclic graph (DAG), where an edge \(u \to v\) means “\(u\) must come before \(v\).” A topological sort produces a linear ordering of the vertices that respects every such constraint, so we can carry out the tasks one at a time without ever doing one before its prerequisite (Kleinberg and Tardos 2005; Cormen et al. 2009).
A topological order exists if and only if the graph is acyclic, so topological sort doubles as a cycle detector for directed graphs.
Problem
Let \(G = (V, E)\) be a directed graph with \(n = |V|\) vertices and \(m = |E|\) edges. A topological order is a permutation \(v_1, v_2, \dots, v_n\) of \(V\) such that every edge \((v_i, v_j) \in E\) satisfies \(i < j\).
A six-vertex DAG and one of its valid topological orders. Sources \(A\) and \(B\) come first, then their successors, then the sink \(F\).
The order is not unique: any source can be emitted first, and any tie among the new sources unlocked by removing it is also valid. For instance, \(B, A, E, C, D, F\) is another correct topological order. What is unique is the set of constraints: every edge of the DAG goes left-to-right in any valid order.
Key Ideas
A topological order exists if and only if the graph is acyclic. The forward direction is immediate: a cycle \(v_{i_1} \to v_{i_2} \to \dots \to v_{i_k} \to v_{i_1}\) cannot have all indices increasing. The reverse direction is what the algorithms below construct.
Two complementary observations drive the standard algorithms:
- A DAG always has a source. A vertex with in-degree zero must exist — otherwise we could walk backward forever and produce a cycle. Emit a source, remove it, and the remaining subgraph is again a DAG. Repeating this peels the order off front-to-back. This is Kahn’s algorithm.
- A DAG always has a sink. Symmetrically, DFS finishes a vertex only after all its descendants have finished, so the first vertex to finish must be a sink. Recording finish times and reversing them produces a topological order from back-to-front. This is the DFS post-order approach.
Both run in \(O(n + m)\) time, and both naturally double as cycle detectors — when no source remains, or when DFS encounters a back-edge.
Algorithm
Kahn’s algorithm: peel sources
Repeatedly emit a source (in-degree zero) and remove it. Maintain a queue of vertices whose in-degree has just dropped to zero.
compute in-degree[v] for every v
S = queue of all v with in-degree[v] == 0
order = []
while S is non-empty:
u = S.dequeue()
order.append(u)
for each edge (u, v):
in-degree[v] -= 1
if in-degree[v] == 0:
S.enqueue(v)
if len(order) < n:
report "graph has a cycle"
else:
return orderDFS post-order: reverse finishing times
Run depth-first search, recording each vertex when its recursive call returns. Reversing the post-order yields a topological order.
visited = {}
order = []
def dfs(u):
visited[u] = True
for each edge (u, v):
if v not visited:
dfs(v)
order.append(u) # post-order
for u in V:
if u not visited:
dfs(u)
return reverse(order)For cycle detection, track the recursion stack with a third color (white/grey/black) as in the DFS cycle-detection example. Encountering a grey successor witnesses a back-edge and therefore a cycle.
Walkthrough
Use the DAG from the figure above: edges \(A \to C\), \(A \to D\), \(B \to D\), \(B \to E\), \(C \to F\), \(D \to F\), \(E \to F\).
Kahn’s algorithm trace
Initial in-degrees: \(A=0\), \(B=0\), \(C=1\), \(D=2\), \(E=1\), \(F=3\).
| Step | Emit | In-degree updates | Queue after step |
|---|---|---|---|
| 1 | A | \(C: 1\to0\), \(D: 2\to1\) | B, C |
| 2 | B | \(D: 1\to0\), \(E: 1\to0\) | C, D, E |
| 3 | C | \(F: 3\to2\) | D, E |
| 4 | D | \(F: 2\to1\) | E |
| 5 | E | \(F: 1\to0\) | F |
| 6 | F | — | empty |
Output order: \(A, B, C, D, E, F\). Every edge in the DAG points left-to-right in this ordering.
Now suppose we add the edge \(F \to A\). Then \(A\)’s in-degree starts at \(1\), so neither \(A\) nor \(F\) is ever added to the queue. After processing \(B\) and the rest, the output would contain only \(5\) vertices. The check len(order) < n catches this: \(5 < 6\), so the algorithm reports a cycle.
DFS post-order trace
Run DFS from \(A\), then from any unvisited remaining vertex, expanding neighbors in alphabetical order. Finish times are recorded as recursive calls return.
| Step | Action | Stack (grey) | Finished (black, in order) |
|---|---|---|---|
| 1 | enter A | A | |
| 2 | enter C (from A) | A, C | |
| 3 | enter F (from C) | A, C, F | |
| 4 | finish F | A, C | F |
| 5 | finish C | A | F, C |
| 6 | enter D (from A) | A, D | F, C |
| 7 | finish D | A | F, C, D |
| 8 | finish A | F, C, D, A | |
| 9 | enter B (new root) | B | F, C, D, A |
| 10 | enter E (from B) | B, E | F, C, D, A |
| 11 | finish E | B | F, C, D, A, E |
| 12 | finish B | F, C, D, A, E, B |
Reversing the finish order gives the topological order \(B, E, A, D, C, F\) — different from Kahn’s order, but every edge still points left-to-right.
Complexity and Tradeoffs
Both algorithms run in \(\Theta(n + m)\) time. Each vertex is processed once and each edge is examined once.
Memory is \(\Theta(n)\) beyond the edge list: an in-degree array and a queue for Kahn’s, a visited set and a recursion stack for DFS.
Important tradeoffs:
- Order produced. Kahn’s emits front-to-back and naturally produces a “level-by-level” order when ties are broken by FIFO. DFS post-order emits back-to-front and tends to keep dependency chains contiguous.
- Iterative vs. recursive. Kahn’s is iterative and avoids deep call stacks — preferable on very deep DAGs in languages with limited recursion depth. DFS is more concise when the traversal is already needed for another reason (e.g., computing finishing times for strongly connected components).
- Cycle detection. Both detect cycles. Kahn’s reports a cycle when fewer than \(n\) vertices are emitted; DFS reports one when it encounters a grey successor.
- Uniqueness. A topological order is unique if and only if at every step exactly one vertex has in-degree zero — equivalently, when the DAG is a linear chain (a Hamiltonian path). In every other case, multiple orders are valid and the algorithm’s tie-breaking rule chooses one.
When to Use It
Use topological sort whenever a problem involves precedence constraints over a finite set of items and the constraint graph is (or should be) acyclic.
- Build systems: compile dependencies before dependents (
make,bazel). - Spreadsheet evaluation: recompute cells in dependency order.
- Course scheduling: take prerequisites first.
- Single-source shortest paths in DAGs: relax edges in topological order to obtain \(O(n + m)\) shortest paths even with negative weights — faster than Bellman-Ford when the graph is acyclic.
- Job scheduling with precedence constraints: needed before applying greedy schedulers like single machine scheduling.
- Cycle detection on directed graphs as a side effect of either algorithm.