Ordering with dependencies
When tasks depend on one another, you need an order where every prerequisite appears before the task that needs it. Topological sort produces such an ordering for a directed acyclic graph. It powers build systems, course scheduling, and dependency resolution.
Counting incoming edges
The most intuitive method tracks in degree, the number of prerequisites still pending for each node.
- Compute the in degree of every node from the dependency edges.
- Put all nodes with zero in degree into a queue, since they have nothing blocking them.
- Repeatedly remove a node from the queue, add it to the order, and decrement the in degree of its neighbors.
- When a neighbor reaches zero in degree, enqueue it.
Each node enters the queue once its last prerequisite is satisfied, so the output respects every dependency.
Detecting impossible orders
If the graph contains a cycle, some nodes never reach zero in degree because they wait on each other forever. When the produced order is shorter than the node count, no valid ordering exists, which is how the algorithm reports a circular dependency.
Key idea
Track each node's pending prerequisites, release nodes whose count hits zero, and a leftover unreleased node signals a cycle with no valid ordering.