Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsTopological sorting algorithms

Kahn's algorithm

Theory

Step after step

Report a typo

Put the steps of Kahn's algorithm into the correct order:

Put the items in the correct order
Get one node out of the queue and add it to the list of the sorted vertices
If the in-degree of the node equals 0 after the reduction, add it to the queue
Put all of the vertices with in-degree equal to 0 in a queue
Reduce the in-degree of the children of the node by one
Count the in-degree for all vertices of the graph
___

Create a free account to access the full topic