How to Implement Topological Sort & Cycle Detection in a DAG (Kahn's Algorithm)
Resolve dependency graphs, build orders, and course prerequisite DAGs in O(V + E) time.
Kahn's algorithm computes the in-degree of every vertex, enqueues all vertices with in-degree 0, and repeatedly pops a vertex u, appends u to the topological order, and decrements the in-degree of its outgoing neighbors v—enqueuing v when in_degree[v] reaches 0. If the resulting order contains fewer than V vertices, the directed graph contains a cycle.
Interactive Runnable CodeSandbox
Kahn's BFS Topological Sort & Cycle Detector
DAG Acyclicity & Linear Extension Criterion
Every vertex in a cycle has in-degree >= 1 within the cycle subgraph and can never reach in-degree 0.
Step-by-Step Implementation Breakdown
Seed Queue with All Zero-In-Degree Source Nodes
Nodes with in-degree 0 have no unmet prerequisites and can be scheduled immediately in parallel.
Detect Cycles by Checking len(order) == num_nodes
If a cycle exists, none of the vertices in the cycle will ever reach in-degree 0, so the BFS terminates early.
Production Edge Cases & Interview Traps
- Disconnected vertices with no edges have in-degree 0 and are naturally included at the start of Kahn's BFS.
Frequently Asked Questions
How can I find the lexicographically smallest topological order?
Replace collections.deque with a min-heap (heapq) so that among all currently available zero-in-degree nodes, the smallest ID is always popped first in O((V + E) log V).