Kahn's algorithm
A topological sort that repeatedly removes a vertex with no remaining incoming edges and lowers the in-degree of its neighbours.
In more detail
Start a queue with every zero in-degree vertex; each time one is removed, append it to the order and decrement its neighbours' in-degrees, enqueuing any that reach zero. If vertices remain when the queue empties, the graph has a cycle. Python's graphlib.TopologicalSorter works the same way.
Related terms
- topological sort — An ordering of a directed graph's vertices in which every edge points from an earlier vertex to a later one.
- in-degree — The number of edges pointing into a vertex of a directed graph; out-degree counts the edges leaving it.
- queue — A collection where items leave in the order they arrived: first in, first out, like a line at a shop counter.
Taught in
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers