Topological sort

Topological sort

Some graphs encode prerequisites, where course A must come before B, or task X before Y. Edges point from a thing to whatever depends on it.

Such a graph has no cycles, and it cannot, since a cycle would mean A requires B which requires A. That structure has a name, a DAG, for directed acyclic graph.

A topological order is any listing of the nodes where every arrow points forward, which is a valid order to take the courses in. There is usually more than one, and any of them will do.

Kahn's algorithm builds one with a counter called indegree, the number of un-taken prerequisites a node still has.

1. Compute every node's indegree.
2. Put all indegree-0 nodes, the ones with no prerequisites, in a queue.
3. Pop a node, append it to the order, and decrement each dependent's indegree. Any dependent that hits 0 joins the queue.

A node reaching indegree 0 means every prerequisite is already in the order, which is what makes appending it safe.

If the finished order is missing nodes, they were stuck on a cycle, which is also how you detect one. The cost is O(V + E), since each node is queued once and each edge decremented once.

topo_order

Running on a familiar DAG, this platform's own course prerequisites.

from collections import deque

def topo_order(graph):
    indegree = {node: 0 for node in graph}
    for node in graph:
        for nxt in graph[node]:
            indegree[nxt] += 1
    queue = deque(node for node in graph if indegree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == len(graph) else None

courses = {
    "intro": ["data structures", "discrete math"],
    "discrete math": ["algorithms"],
    "data structures": ["algorithms"],
    "algorithms": ["interviews"],
    "interviews": [],
}
print(topo_order(courses))
print(topo_order({"a": ["b"], "b": ["a"]}))

Output

['intro', 'data structures', 'discrete math', 'algorithms', 'interviews']
None

The first loop counts arrows arriving at each node, and it walks the adjacency lists rather than the nodes, which is why it is O(E).

Only intro starts at indegree 0, so it is the only node in the initial queue. Algorithms starts at 2, waiting on both data structures and discrete math.

Algorithms appears after both of its prerequisites, which is the guarantee doing its job. Its indegree drops to 1 and then to 0, and only the second decrement queues it.

The order between data structures and discrete math is arbitrary, since nothing connects them. A stack instead of a queue would produce a different but equally valid order.

The two-node cycle returns None, because neither a nor b ever reaches indegree 0 and the order comes out empty.

Nodes on a cycle never reach indegree 0, so they never enter the queue, and the finished order comes out shorter than the node count.

Each node in a cycle waits on another cycle member, and that member is waiting right back, so no decrement ever brings either to zero.

Nothing dramatic happens. The algorithm ends peacefully when the queue empties, having emitted every node that was not blocked, and the incomplete order is the only evidence.

The length check len(order) == len(graph) turns that into a clean yes or no answer. Nodes downstream of a cycle are also missing, since they are waiting on something that never finishes.

"Can these courses be finished at all?" is exactly this check, and it is the same question as whether a build graph or a spreadsheet has a circular dependency.

That makes Kahn's algorithm two tools in one. Any topological-sort implementation is also a cycle detector, at no extra cost.

min_semesters

Processing the DAG in waves rather than one node at a time.

def min_semesters(graph):
    indegree = {n: 0 for n in graph}
    for n in graph:
        for nxt in graph[n]:
            indegree[nxt] += 1
    current = [n for n in graph if indegree[n] == 0]
    semesters = 0
    done = 0
    while current:
        semesters += 1
        next_level = []
        for node in current:
            done += 1
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    next_level.append(nxt)
        current = next_level
    return semesters if done == len(graph) else -1

courses = {
    "intro": ["data structures", "discrete math"],
    "discrete math": ["algorithms"],
    "data structures": ["algorithms"],
    "algorithms": ["interviews"],
    "interviews": [],
}
print(min_semesters(courses))
print(min_semesters({"a": ["b"], "b": ["a"]}))

Output

4
-1

This is Kahn's algorithm processed level by level, exactly like the BFS rings in lesson 7-2. Everything currently unblocked is taken in parallel.

Holding a whole level in current and building next_level separately is what keeps the waves distinct. A single queue would blur them, since a node unlocked this level would be popped in the same pass.

The four waves are intro, then data structures and discrete math together, then algorithms, then interviews.

done counts processed nodes so the cycle check still works, and the wave version needs its own counter because order no longer exists as a single list.

The answer 4 is also the longest path through the DAG, which is the general fact worth naming. The minimum number of waves equals the longest prerequisite chain, since nothing can compress that chain.

It is computing a topological order.

Imports form a DAG, since a module must be compiled after everything it imports and imports never cycle, which is exactly the prerequisite structure from this lesson.

Build systems, spreadsheet formula evaluation, and course planners all run topological sorts, and so do package managers deciding install order.

Real build systems also use the wave version from the previous block, because nodes in the same wave have no dependency between them and can compile in parallel.

In interviews the trigger words are prerequisites, dependencies, or must-come-before, and your answer starts with indegrees and a queue.

Mentioning the cycle case unprompted is worth points, since a real build system has to report a circular import rather than loop forever.