Peeling off sources
Kahn's algorithm builds a topological order without recursion by tracking each node's in degree, the count of incoming edges. A node with in degree zero has no prerequisites, so it can be placed next in the order.
The loop
Start by enqueuing every node whose in degree is already zero. Repeatedly pop a node, append it to the output, and decrement the in degree of each successor. Whenever a successor's in degree hits zero, enqueue it.
- Enqueue all nodes with no incoming edges.
- Pop one, output it, and reduce successor in degrees.
- Enqueue any successor that reaches in degree zero.
Cycle detection
If the output ends up shorter than the node count, some nodes never reached in degree zero, which means the graph contains a cycle and no topological order exists.
Key idea
Kahn's algorithm repeatedly removes nodes with no incoming edges to build a topological order, and a leftover set of nodes reveals a cycle that makes ordering impossible.