Topological Sort
Intermediate · 18 min read · Problem-Solving Patterns, Graphs
Order tasks with dependencies and detect cycles (Kahn's algorithm).
"You must take Algorithms before Machine Learning, and Data Structures before Algorithms. In what order can you take all courses — or is it impossible?" Whenever things have dependencies, you're looking at a directed graph, and the question "what order respects every dependency?" is a topological sort.
The idea: start with what's ready
A task is ready when all its prerequisites are done — when its in-degree (the number of incoming edges) is 0. Take any ready task, mark it done, and reduce the in-degree of everything that depended on it. Anything that drops to 0 becomes ready. This is Kahn's algorithm.
The DFS version: three colours
DFS finds a topological order too: a node can be placed only after everything that depends on it has finished, so the reverse of the finishing order is a valid order. To detect cycles, track three states:
Worked problems
Process Kahn's queue level by level (freeze the size, like tree BFS); each level is one semester in which all ready courses are taken together. The number of levels is the answer (or −1 if a cycle prevents finishing).
Practice ladder
Interview questions
- How does Kahn's algorithm detect a cycle?
- Why does DFS cycle detection in a directed graph need three states rather than a visited boolean?
Further reading
Key takeaways
- Dependencies → directed graph → topological sort; an order exists if and only if there's no cycle.
- Kahn's: start with in-degree 0, remove, decrement neighbours, repeat; output shorter than n means a cycle.
- DFS: reverse finishing order, with three states to detect cycles correctly.
- Level-by-level Kahn's counts parallel rounds; a heap instead of a queue gives the smallest order.
- Double-check the edge direction.