In software build graphs and task schedulers, Kahn’s Algorithm (Indegree BFS) is universally favored over recursive DFS for two huge reasons:

1. No Recursion / Call-Stack Exhaustion: DFS recursion on a graph with 500,000 chained dependencies will instantly crash with a stack overflow (RecursionError or OS segfault). Kahn’s algorithm runs iteratively using a queue in heap memory.
2. Trivial Cycle Detection: With DFS, cycle detection requires tracking 3 node states (Unvisited, Visiting, Visited). With Kahn’s algorithm, cycle detection is automatic: if the number of sorted nodes is less than total nodes, a cycle exists!

The Plain English Mental Model of Kahn’s Algorithm

Think about taking university courses. A course with indegree = 0 has zero prerequisites—you can enroll in it on Day 1!

1. Count the indegree (number of incoming dependency arrows) for every single node.
2. Find all nodes with indegree == 0 and push them into a queue (these tasks can run immediately).
3. While the queue is not empty:
   • Pop a task u and add it to your execution plan.
   • For every task v that depended on u, decrement its indegree (indegree[v]--).
   • If indegree[v] == 0, all its prerequisites are now satisfied! Push it into the queue!

If there was a circular dependency (e.g., A depends on B and B depends on A), their indegrees will never reach 0, so they will never enter the queue!

Clean Python 3.12 Implementation

from collections import deque

def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
    """Returns topological execution order in O(V + E) time, or [] if cycle detected."""
    adj = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    # Build adjacency list: [prereq -> course]
    for dest, src in prerequisites:
        adj[src].append(dest)
        indegree[dest] += 1

    # Initialize queue with all nodes having 0 prerequisites
    queue = deque([i for i in range(num_courses) if indegree[i] == 0])
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)

        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    # If order doesn't contain all courses, a cyclic dependency exists!
    if len(order) != num_courses:
        return []

    return order

Complexity Breakdown

• Time Complexity: O(V + E). We touch every vertex and edge exactly once.
• Space Complexity: O(V + E) to store the adjacency list and indegree table.