Topological sort
Some graphs encode prerequisites: course A must come before B, task X before Y. Edges point from a thing to what depends on it, and there are no cycles (a cycle would mean A requires B requires A). That structure is a DAG: directed acyclic graph.
A topological order is any listing of the nodes where every arrow points forward, a valid order to take the courses in.
Kahn's algorithm builds one with a counter called indegree: how many un-taken prerequisites a node still has.
- Compute every node's indegree.
- Put all indegree-0 nodes (no prerequisites) in a queue.
- Pop a node, append it to the order, and decrement each dependent's indegree. Any dependent that hits 0 joins the queue.
If the finished order is missing nodes, they were stuck on a cycle, which is also how you detect cycles.
Code exercise · python
Run this on a familiar DAG: this platform's own course prerequisites. Then watch the two-node cycle come back as None.
Quiz
How does Kahn's algorithm detect that the prerequisites contain a cycle?
Code exercise · python
Your turn. Process the DAG in WAVES: everything with indegree 0 is semester 1, everything unlocked by semester 1 is semester 2, and so on. Return the number of semesters to finish all courses, or -1 on a cycle.
Problem
A build system must compile modules so that every module compiles after everything it imports, and imports never form a cycle. What kind of ordering is it computing?