Topological Sort
Orders a DAG so every edge points forward — dependencies before dependents. Kahn's algorithm repeatedly emits any node whose in-degree has dropped to zero. Build systems live on this.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
compute in-degrees emit any node with in-degree 0 remove its edges, repeat emitted order is valid
Reference implementation
# Kahn's algorithm
q = [n for n in V if indeg[n] == 0]
while q:
n = q.pop(0); order.append(n)
for m in out[n]:
indeg[m] -= 1
if indeg[m] == 0: q.append(m)