Topological Sort
What must come first.
You can't put your shoes on before your socks. Some tasks must come before others. Given a list of these rules, topological sort finds an order that obeys every one of them. Build tools, course plans, and spreadsheets all use it.

- Socks before shoes
- Some tasks must come first
- Find an order that obeys every rule
Kahn's algorithm
Each task maps to the tasks that depend on it. First, we count how many tasks must happen before each one. Tasks with a count of zero can start right away, so they go in a queue. Each time we finish a task, its dependants get one step closer, and any that reach zero join the queue. Run it. Underwear, socks, and the shirt come first, and the coat comes last.
from collections import deque
before = {"underwear": ["trousers"], "socks": ["shoes"],
"trousers": ["shoes", "belt"], "shirt": ["belt", "coat"],
"belt": ["coat"], "shoes": [], "coat": []}
need = {t: 0 for t in before}
for deps in before.values():
for d in deps:
need[d] += 1
queue = deque(t for t in before if need[t] == 0)
order = []
while queue:
t = queue.popleft()
order.append(t)
for d in before[t]:
need[d] -= 1
if need[d] == 0: queue.append(d)
print(order)['underwear', 'socks', 'shirt', 'trousers', 'shoes', 'belt', 'coat']
Cycles break it
If the rules form a loop, like A before B, and B before A, there's no valid order. Kahn's algorithm notices, because some tasks never reach zero, and the final order is shorter than the task list. That's how build tools report a circular dependency. It all runs in O of V plus E.
| key | value |
|---|---|
| Count incoming | how many must come first |
| Zero | ready to start |
| Finish one | decrement its dependants |
| Order too short | there's a cycle |
Summary
Topological sort orders tasks so every rule is obeyed. Count what must come first, start with zeros, and release tasks as their counts drop. Next, a structure for tracking groups. Union find.
Key takeaways- Count prerequisites
- Start with zeros
- Short order = cycle