Ordering by dependency
A topological sort arranges the vertices of a directed acyclic graph so that every edge points forward in the order. It answers questions like which order to run tasks where some depend on others, or how to schedule course prerequisites.
Kahn's method
Kahn's algorithm builds the order using in degrees, the count of incoming edges per vertex.
- Compute the in degree of every vertex.
- Place all vertices with in degree zero into a queue; these have no prerequisites.
- Repeatedly remove a vertex from the queue, append it to the output order, and decrement the in degree of each of its successors.
- Whenever a successor's in degree drops to zero, it has no remaining prerequisites, so enqueue it.
Detecting impossibility
If the output ends up containing fewer vertices than the graph holds, some vertices never reached in degree zero. That can only happen because they sit inside a cycle, which means no valid topological order exists. So Kahn's algorithm doubles as a cycle detector.
The work is linear in vertices plus edges, since each edge is relaxed exactly once when its source is removed.
Key idea
Kahn's algorithm peels off vertices with no remaining incoming edges into a queue, producing a valid topological order and flagging a cycle if any vertices are left behind.