Kahn's algorithm

Kahn’s algorithm (1962) sorts a DAG in topological order by the following process:

1. for every node, count how many predecessors feed into it (in-degree). Any node with a count of zero is ready
2. pick any zero-count node and append it to the sorted output
3. For each node that depends on the one just appended, subtract 1 from its in-degree; if that count reaches zero, the node becomes ready.
4. loop until empty. If there is any node left, there is a cycle (the graph is not a DAG)

It’s time complexity is .

Below is the pseudocode:

let sorted = []
let in_degrees = << number of incoming edge of each node >>
let queue = << all nodes with in-degree 0 >>
 
while queue is not empty:
    n: node = queue.dequeue()
    sorted.push_back(n)
    for each node m with an edge e from n to m:
        in_degrees[m] -= 1
        if in_degrees[m] == 0:
            queue.enqueue(m)
 
# If still have edges not processed, alternatively we can check whether the sorted list has the same size as the number of nodes
if in_degree is not all 0:
    << has cycle >>
else:
    return sorted

Note

the queue above can be replaced by another data structure, such as a stack or a priority queue. When more than one valid topological order exists, the choice of data structure can change which order is produced, but the result will always be correct