Kahn's Algorithm: BFS Topological Sort

A topological sort of a Directed Acyclic Graph (DAG) is an ordering of its nodes such that every directed edge u → v means u comes before v in the ordering. It represents a valid execution order for tasks with dependencies — like build systems, course scheduling, or package management. Only DAGs have valid topological orderings; a cycle makes it impossible.

Kahn's Algorithm is a BFS-based approach to topological sort. The key insight: a node with in-degree 0 (no prerequisites) can be placed first in the ordering. After placing it, remove it and decrement the in-degree of its neighbours. New zero-in-degree nodes become available. Repeat until all nodes are placed or a cycle is detected (nodes remain with non-zero in-degree).