AI Hints
Home›DSA in Python Tutorial›Weighted Graphs
DSA in Python · Lesson 84 of 132

Topological Sort

What must come first.

⏱ 2 min read▶ Video at 1:39:41🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Topological Sort
From the video: Topological Sort
  • 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.

topo.pypython
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)
Output
['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.

keyvalue
Count incominghow many must come first
Zeroready to start
Finish onedecrement its dependants
Order too shortthere'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
Next up: Union Find — tracking connected groups