Topological Sort
Ordering tasks so every dependency comes first - course schedules, build systems - and how it detects cycles along the way.
On this page
Some problems are about order under dependencies: which course before which, which build task before which, which step of a recipe before which. When each item depends on others finishing first, you need a topological sort - a linear ordering of a directed graph where every edge points forward. It also detects the one thing that makes ordering impossible: a cycle.
The problem it solves
Given a directed acyclic graph (DAG) where an edge a → b means "a must come before b," a
topological sort produces an order in which every node appears before all nodes that depend on it. There
can be several valid orders; you just need one.
Kahn's algorithm (BFS on in-degrees)
The cleanest approach counts each node's in-degree (how many prerequisites point at it). Nodes with in-degree 0 have no unmet dependencies, so they can go first. Remove them, decrement their neighbors' in-degrees, and repeat:
// topological sort via Kahn's algorithm — O(V + E)
List<Integer> topoSort(int n, Map<Integer, List<Integer>> graph) {
int[] indegree = new int[n];
for (var edges : graph.values())
for (int to : edges) indegree[to]++;
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++)
if (indegree[i] == 0) queue.offer(i); // no prerequisites → ready
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int next : graph.getOrDefault(node, List.of()))
if (--indegree[next] == 0) queue.offer(next); // its last prereq is done
}
return order.size() == n ? order : List.of(); // fewer than n → a cycle exists
}Cycle detection comes free
Here's the elegant part: if the graph has a cycle, the nodes in that cycle never reach in-degree 0 (each waits on another in the loop), so they never enter the queue. If the final order contains fewer than n nodes, a cycle exists and no valid ordering is possible. So topological sort answers "can these tasks be ordered at all?" as a side effect.
The tell for topological sort
Reach for topological sort whenever a problem says 'A must come before B,' 'prerequisites,' 'build order,' 'course schedule,' or 'resolve dependencies.' If it also asks 'is it even possible?', that's the cycle-detection half. DFS-based topological sort (postorder, then reverse) is an equally valid alternative to Kahn's algorithm.
You can't put your shoes on before your socks, or your coat before your shirt - some garments depend on others being on first. A topological sort is a valid dressing order: it lists each garment only after everything it depends on. There are several valid orders (socks-then-shirt or shirt-then-socks, since they don't depend on each other), and you only need one. But if your rules ever formed a loop - 'belt before trousers, trousers before belt' - no order could satisfy them, and you'd be stuck forever: that impossible loop is the cycle topological sort detects.
Given numCourses and a list of prerequisite pairs [a, b] meaning "b must be taken before a," determine whether you can finish all courses. Describe how topological sort answers this and what specifically signals that you cannot.
In Kahn's topological sort, what indicates the graph has a cycle (no valid ordering)?
Key takeaways
- Topological sort linearly orders a directed acyclic graph so every edge points forward - each node before its dependents.
- It solves dependency/order problems: course schedules, build order, task sequencing.
- Kahn's algorithm: repeatedly take nodes with in-degree 0, remove them, and decrement neighbors' in-degrees - O(V + E).
- Cycle detection is free: if fewer than n nodes are ordered, a cycle exists and no valid order is possible.
- The tell is 'A before B', 'prerequisites', or 'is a valid order even possible?'