Topological Sort

Description

Tasks with prerequisites, such as courses, build steps or package installs, need an order in which every task comes after everything it depends on. That's a topological order of a directed graph, and one exists exactly when the graph has no cycle. Usually there are many valid orders, so the problem has to say which one it wants. This skill covers Kahn's algorithm, how ties are broken, and the round-by-round version that counts semesters.

We'll go from simple to more technical:

1. The pattern: Kahn's algorithm, taking ready tasks from a min-heap.
2. A second flavor: rounds, where each round takes everything ready at once.
3. Where topological order runs in production (builds, installs, schedulers).
4. What breaks it: tie rules, a short result, and rounds that merge.

The approach

List<Integer> topoSort(int n, List<List<Integer>> adj) {
    int[] indegree = new int[n];
    for (List<Integer> next : adj) for (int v : next) indegree[v]++;

    PriorityQueue<Integer> ready = new PriorityQueue<>();      // min-heap: smallest ready node first
    for (int v = 0; v < n; v++) if (indegree[v] == 0) ready.add(v);

    List<Integer> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        int node = ready.poll();
        order.add(node);
        for (int next : adj.get(node)) {
            if (--indegree[next] == 0) ready.add(next);        // its last prerequisite just finished
        }
    }
    return order;                                               // shorter than n means there was a cycle
}

import heapq


def topo_sort(n: int, adj: list[list[int]]) -> list[int]:
    indegree = [0] * n
    for targets in adj:
        for v in targets:
            indegree[v] += 1

    ready = [v for v in range(n) if indegree[v] == 0]
    heapq.heapify(ready)                         # min-heap: smallest ready node first

    order = []
    while ready:
        node = heapq.heappop(ready)
        order.append(node)
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:               # its last prerequisite just finished
                heapq.heappush(ready, nxt)
    return order                                 # shorter than n means there was a cycle

Kahn's algorithm keeps a pool of "ready" nodes - in-degree zero, nothing left to wait for. Taking one removes its outgoing edges, which may make others ready. Any node taken has had all its prerequisites taken before it, so the order is valid. The pool's type decides which valid order: a min-heap always takes the smallest ready node, which produces the unique lexicographically smallest order. On 5->2, 5->0, 4->0, 4->1, 2->3, 3->1 the heap gives 4 5 0 2 3 1; a plain FIFO queue gives 4 5 2 0 3 1 - also valid, just different.

A second flavor: rounds instead of a list

Process the ready pool in rounds - everything ready now, then everything that became ready because of them - and the number of rounds is the minimum number of "semesters" needed if any number of independent tasks can run in parallel:

int rounds = 0, taken = 0;
while (!ready.isEmpty()) {
    rounds++;
    int size = ready.size();                 // snapshot: only what's ready at the start of this round
    for (int i = 0; i < size; i++) {
        int u = ready.poll();
        taken++;
        for (int v : adj.get(u)) if (--indegree[v] == 0) ready.add(v);
    }
}
return taken == n ? rounds : -1;             // -1: a cycle - some tasks can never start

rounds = taken = 0
while ready:
    rounds += 1
    for _ in range(len(ready)):          # range() reads the size once: only what's ready now
        u = ready.popleft()
        taken += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                ready.append(v)
result = rounds if taken == n else -1    # -1: a cycle - some tasks can never start

The round count equals the number of nodes on the longest dependency chain. It's the same level-by-level BFS shape as tree level order, including its classic bug: re-reading ready.size() in the loop condition lets newly ready nodes slip into the current round. (In Python, for _ in range(len(ready)) reads the size once; an inner while ready: has the bug.)

Where you'll see it

Build systems, package managers, database migration runners, spreadsheet recalculation and task schedulers all compute a topological order of their dependency graph first. The round-by-round version is how schedulers find the critical path - the minimum number of stages when independent jobs run in parallel. A fixed tie-break (like the min-heap) makes the order independent of how inputs happened to be listed, which matters for reproducible builds.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Kahn's algorithm with a FIFO queue is run twice on the same input. Can the outputs differ?

2. The topological sort returns 4 nodes for a 6-node graph. What happened?

3. Why does processing Kahn's algorithm in rounds give the minimum number of semesters?

Key takeaways

• A topological order exists exactly when the directed graph has no cycle.
• Kahn's algorithm repeatedly takes a node with no remaining prerequisites; a result shorter than n means a cycle.
• The ready pool's type picks the order: a min-heap gives the lexicographically smallest (O(V log V + E)); a FIFO queue is deterministic but input-order dependent (O(V + E)).
• Processing in rounds (with a size snapshot) counts the minimum number of parallel stages - the longest dependency chain.
• DFS finish order, reversed, is also a topological order.