Topological Sort

What topological sort is

A topological order of a directed graph lists nodes so that every edge points forward: if A must precede B, A appears before B. It exists exactly when the graph has no directed cycle - a cycle means mutually blocking requirements with no valid order at all. Orders are generally not unique; any answer respecting all edges is correct.

The interview workhorse is Kahn's algorithm: repeatedly take a node with no remaining prerequisites (indegree 0), emit it, and 'complete' it by decrementing its dependents' indegrees, enqueueing any that reach zero. It sorts and cycle-checks in one pass: if fewer than n nodes are emitted, the leftovers form or feed a cycle.

How to recognize it

Signals: 'prerequisites', 'build/task order', 'must come before', dependency resolution, or any 'is this set of constraints satisfiable' over ordered pairs. Course schedule is the canonical costume; build systems and spreadsheet formula evaluation are the real-world versions worth mentioning.

Sequencing questions where dependency chains determine timing also live here - 'minimum semesters needed' is the number of BFS layers in Kahn's processing, i.e. the longest chain of prerequisites.

Kahn's algorithm

Build an adjacency list (prerequisite -> dependents) and an indegree array in one pass over the edges. Seed a queue with all indegree-0 nodes - independent starting points. Loop: pop, append to the order, decrement each dependent, enqueue those hitting zero. Count what you emit.

build adj (pre -> list of dependents) and indegree[]
queue = all nodes with indegree 0
order = []
while queue not empty:
    node = queue.pop_front()
    order.append(node)
    for next in adj[node]:
        indegree[next] -= 1
        if indegree[next] == 0:
            queue.push_back(next)
return order if len(order) == n else CYCLE

The DFS alternative

Post-order DFS also topologically sorts: finish all of a node's descendants, then prepend the node (or reverse the finish order). Cycle detection needs three colors - unvisited, in-progress, done - where meeting an in-progress node means a back edge, hence a cycle. Kahn's is usually the safer interview pick: iterative, counting-based cycle detection, and it naturally yields the layer structure that 'minimum rounds' questions need.

Common pitfalls

Reversing edge direction when building the graph - 'a requires b' means edge b -> a (b unlocks a). Drawing one edge before coding prevents the whole class of bugs.

Forgetting the emitted-count check: without comparing against n, cyclic inputs return a silently truncated 'order'.

Seeding the queue with only one zero-indegree node when several exist - all of them start available.

Using plain DFS cycle detection with a single visited boolean - it cannot distinguish 'visited earlier, fine' from 'still on the current path, cycle'; the in-progress state is mandatory.

Assuming the order is unique or lexicographic - if a problem demands the smallest order, the queue becomes a min-heap, at O(log n) per operation.

Worked examples

for (a, b) in prerequisites:
    adj[b].append(a); indegree[a] += 1
queue = courses with indegree 0
done = 0
while queue not empty:
    c = queue.pop_front(); done += 1
    for next in adj[c]:
        indegree[next] -= 1
        if indegree[next] == 0: queue.push_back(next)
return done == numCourses

# same as course schedule, plus:
order = []
... on dequeue: order.append(course) ...
return len(order) == numCourses ? order : []

if n <= 2: return all nodes
leaves = nodes with degree 1
remaining = n
while remaining > 2:
    remaining -= len(leaves)
    next_leaves = []
    for leaf in leaves:
        neighbor = its remaining neighbor
        degree[neighbor] -= 1
        if degree[neighbor] == 1: next_leaves.append(neighbor)
    leaves = next_leaves
return leaves

Check yourself

Try to answer before revealing - retrieving from memory is what makes it stick.

Frequently asked questions