Topological Sort
A topological sort arranges the nodes of a directed acyclic graph into a line so that every edge points forward. If task A must happen before task B, then A appears before B in the ordering. It answers questions like build order and course prerequisites.
Kahn's algorithm
One approach tracks each node's in degree, the number of edges pointing into it. Start by enqueuing every node with in degree zero, since they depend on nothing. Then repeatedly:
- Remove a node with no remaining dependencies and append it to the output.
- Decrease the in degree of each neighbor.
- Enqueue any neighbor whose in degree just hit zero.
When the queue empties, you have a valid ordering, unless some nodes never reached zero.
Detecting cycles
A topological order exists only if the graph has no cycles. If Kahn's algorithm finishes with nodes still unprocessed, those nodes form a cycle, signaling impossible dependencies. The whole process is linear in nodes plus edges.
Key idea
Topological sort lines up a directed acyclic graph so dependencies always precede dependents, and leftover nodes reveal a cycle.