Topological Sort (Kahn)

A queue-based topological sort. Nodes with no remaining prerequisites (in-degree 0) are emitted; removing them frees their dependents. Leftover nodes would indicate a cycle.

Category

Graphs

Time complexity

O(V + E)

Space complexity

O(V)

Pseudocode

queue all in-degree-0 nodes
pop one, append to order
  decrement neighbours’ in-degree
  enqueue any that hit 0

Reference implementation

q = [n for n in V if indeg[n] == 0]
while q:
    n = q.pop(0); order.append(n)
    for m in adj[n]:
        indeg[m] -= 1
        if indeg[m] == 0: q.append(m)

Open the interactive Topological Sort (Kahn) visualisation →