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

Taught in

References