Topological Sort Explained: Course Scheduling With Kahn's Algorithm

"There are n courses and a list of prerequisite pairs. Can you finish them all, and in what order?" It reads like a puzzle about a university, but it is the same question a build system asks about source files, a package manager asks about dependencies, and a spreadsheet asks about formulas. The answer to all of them is a topological sort.

The problem it solves

You have tasks and "must happen before" rules. You want any order that respects every rule — or proof that no such order exists.

Brute force means trying orderings: there are n! of them, and checking each against the rules. That is hopeless beyond a dozen courses. Yet the rules contain far more structure than a pile of permutations: some courses need nothing at all, and taking one can only ever free others, never block them.

The intuition

Model each course as a node and each prerequisite as an arrow from the course you need to the course it unlocks. Now count, for every course, how many arrows point into it — how many prerequisites it is still waiting on. That number is its in-degree.

A course with in-degree zero is ready: nothing is blocking it. Take it. Taking it removes its outgoing arrows, so every course it unlocks drops by one. Anything that hits zero becomes ready too. Repeat until nothing is ready.

That is Kahn's algorithm, and it has a lovely property: it never needs to look ahead or undo anything. Every decision is final, because a course only becomes ready once all of its prerequisites are already in the output.

If the queue empties while courses remain, those courses are waiting on each other. Nothing outside the group can ever unblock them, so the leftovers are a cycle.

That second half is the part people forget. Kahn's algorithm is not just an ordering routine; it is also a cycle detector, for free. Count the output. If it is shorter than n, there is no valid order, and the courses never taken tell you where the cycle lives.

Watch it run

The flat-pack example from the lesson: the number above each step is how many blockers it is still waiting on, and the ready row holds every step at zero. Watch a step leave the ready row, and watch the counts of the steps it unlocks tick down. Nothing ever becomes ready early.

Notice that frame and legs become ready at the same moment. Either can go first; both orders are correct. A topological order is usually not unique, which matters when an interviewer's test expects one particular answer — ask whether any valid order is accepted.

The code

from collections import deque

def course_order(n, prereqs):
    """prereqs: list of (course, needs). Returns an order, or None on a cycle."""
    unlocks = [[] for _ in range(n)]
    waiting = [0] * n                        # in-degree: unmet prerequisites
    for course, needs in prereqs:
        unlocks[needs].append(course)
        waiting[course] += 1
    ready = deque(c for c in range(n) if waiting[c] == 0)
    order = []
    while ready:
        c = ready.popleft()
        order.append(c)
        for nxt in unlocks[c]:
            waiting[nxt] -= 1
            if waiting[nxt] == 0:            # its last prerequisite just cleared
                ready.append(nxt)
    return order if len(order) == n else None

print(course_order(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))   # [0, 1, 2, 3]
print(course_order(3, [(0, 1), (1, 2), (2, 1)]))           # None
print(course_order(3, []))                                  # [0, 1, 2]

The second call has courses 1 and 2 requiring each other. Course 0 needs 1, so it is stuck too — the output is empty, and None comes back.

To trust it, compare it with the definition itself on small random graphs: a valid order exists exactly when some permutation satisfies every rule.

from itertools import permutations
import random

def valid(order, prereqs):
    pos = {c: i for i, c in enumerate(order)}
    return all(pos[needs] < pos[course] for course, needs in prereqs)

random.seed(3)
agree = 0
for _ in range(3000):
    n = random.randint(1, 6)
    edges = list({(random.randrange(n), random.randrange(n))
                  for _ in range(random.randint(0, 8))})
    got = course_order(n, edges)
    possible = any(valid(p, edges) for p in permutations(range(n)))
    if got is None:
        agree += not possible
    else:
        agree += valid(got, edges)
print(agree)                                               # 3000

Three thousand graphs, including self-loops and cycles, and Kahn's answer matched the brute force every time.

The common follow-up is "what is the minimum number of semesters, if you can take any number of courses at once?" Process the ready set one whole layer at a time instead of one course at a time, and count the layers:

def semesters(n, prereqs):
    unlocks = [[] for _ in range(n)]
    waiting = [0] * n
    for course, needs in prereqs:
        unlocks[needs].append(course)
        waiting[course] += 1
    layer = [c for c in range(n) if waiting[c] == 0]
    taken = count = 0
    while layer:                             # everything in a layer runs in parallel
        count += 1
        taken += len(layer)
        nxt = []
        for c in layer:
            for m in unlocks[c]:
                waiting[m] -= 1
                if waiting[m] == 0:
                    nxt.append(m)
        layer = nxt
    return count if taken == n else -1

print(semesters(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))      # 3
print(semesters(3, [(0, 1), (1, 2), (2, 1)]))              # -1

It is the same algorithm with the same structure as breadth-first search by levels. The layer count equals the longest chain of prerequisites.

The complexity

Building the adjacency list and in-degrees touches every course and every rule once. The main loop takes each course off the queue once and decrements along each rule once. Total: O(V + E) time and O(V + E) space. Nothing is sorted and nothing is revisited.

Where it goes wrong

• Edge direction backwards. "Course 1 requires course 0" is an arrow from 0 to 1. Flip it and you get the reverse order, which looks plausible on small examples and fails on the rest.
• Forgetting the cycle check. Returning order without comparing its length to n silently gives a partial schedule for an impossible input.
• Using a list as a queue. list.pop(0) is O(n); on large graphs that turns the whole algorithm quadratic. Use deque.
• Needing a specific order. For "the lexicographically smallest valid order", swap the queue for a min-heap. The logic is unchanged; the cost rises to O(V log V + E).

The DFS alternative — finish-time order with three-colour cycle detection — is equally valid, and is covered in directed cycle detection. Kahn's version tends to be easier to explain under pressure because it has no recursion.

How to say it in an interview

"This is a topological sort on a directed graph where an edge means 'must come before'. I'll use Kahn's algorithm: compute each node's in-degree, start with every node at zero, and repeatedly take one, decrementing its neighbours and enqueueing any that reach zero. If I output fewer than n nodes, the rest form a cycle, so there's no valid order. It's O(V + E)."

If they ask for the minimum number of rounds, say "same thing, processed one layer at a time" — and you have already answered the follow-up.