Topological Sort: Doing Things in Order

Tasks that depend on other tasks

Some things must happen before others: you put on socks before shoes, and take Python before DSA. Draw an arrow from each task to the tasks that depend on it. A topological order lists the tasks so every arrow points forward.

Kahn's algorithm

• Count, for each task, how many arrows point into it (its in-degree): how many prerequisites it still needs.
• Tasks with in-degree 0 are ready – put them in a queue.
• Take a ready task, add it to the order, and “tick off” one prerequisite for everything that depends on it. Any task that reaches 0 becomes ready.

from collections import deque

needs = {                       # task -> tasks that must come first
    "shoes": ["socks", "trousers"],
    "trousers": ["underwear"],
    "socks": [],
    "underwear": [],
    "belt": ["trousers"],
}

after = {t: [] for t in needs}  # task -> tasks that depend on it
indegree = {t: len(pre) for t, pre in needs.items()}
for task, pre in needs.items():
    for p in pre:
        after[p].append(task)

ready = deque(sorted(t for t in needs if indegree[t] == 0))
order = []
while ready:
    task = ready.popleft()
    order.append(task)
    for nxt in after[task]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            ready.append(nxt)
print(order)

Output

['socks', 'underwear', 'trousers', 'shoes', 'belt']

Impossible orders

If A needs B and B needs A, there's a cycle and no valid order exists. Kahn's algorithm notices: some tasks never become ready, so the order ends up shorter than the number of tasks.

Tip: Build systems, spreadsheet formulas and course planners all use topological sort.