Topological Sort

A topological sort puts the nodes of a directed graph in an order where every arrow points forward — if there is an edge A -> C, then A comes before C in the line-up. It is how you schedule tasks when some must finish before others can start: course prerequisites, build steps, package installs.

Intuition

Think of a course catalog. C (say, Data Structures) needs both A and B first. D and E both need C. You cannot take a course until every prerequisite is checked off.

So you scan for any course with zero unmet prerequisites and take it. Taking it "uses up" that prerequisite for the courses that depended on it, which might drop one of them to zero unmet prerequisites — now it is takeable too. The order in which you take courses, start to finish, is a valid topological order.

Walk through it

Step through the animation on the right. Each node shows a badge with its current in-degree: how many arrows still point into it. At the start A and B are 0 (no prerequisites), C is 2, D and E are 1.

We seed a queue with the zero-in-degree nodes (A, B), then loop: pop one, append it to the order strip along the bottom, and walk its outgoing edges, dropping each neighbor's in-degree by one. When C finally hits 0 it joins the queue; emitting C then drops D and E to 0. The final order is A, B, C, D, E — every arrow points forward.

The code, line by line

from collections import deque
 
def topo_sort(graph, nodes):
    indeg = {u: 0 for u in nodes}
    for u in nodes:
        for v in graph[u]:
            indeg[v] += 1
 
    queue = deque(u for u in nodes if indeg[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
 
    if len(order) != len(nodes):
        raise ValueError("graph has a cycle")
    return order

• Lines 4-7 build the indeg map: every edge u -> v adds one to v's in-degree.
• Line 9 seeds the queue with every node that already has in-degree 0 — the nodes with no prerequisites.
• Lines 11-13 are the main loop: pop the front node and append it to the result.
• Lines 14-17 "remove" the popped node's edges by decrementing each neighbor's in-degree. The moment a neighbor reaches 0, it has no remaining prerequisites, so we enqueue it.
• Lines 19-20 are the cycle check: if we could not emit every node, some nodes are stuck in a cycle (each waiting on the other), and no valid ordering exists.

Complexity

Every node enters and leaves the queue exactly once, and every edge is looked at exactly once when its source node is processed — so the work is linear in V + E. The extra space is O(V) for the in-degree map and the queue.

When to use / pitfalls

Practice