Graph Algorithm

Kahn's Algorithm

“The Dependency Resolver”

Time: O(V + E)

Space: O(V)

Output: Topological Ordering (Linear Sequence)

History

If you have ever been stuck in "Dependency Hell" while trying to install a node module, you have Arthur Kahn (1962) to thank for the solution.

This is the standard algorithm for Topological Sorting. It takes a graph of tasks where some tasks must finish before others can start (a Directed Acyclic Graph, or DAG) and flattens it into a linear to-do list.

How It Works

Kahn's algorithm simulates a production line. It keeps track of "Indegrees" -- the number of prerequisites a task has left.

The Algorithm Step-by-Step

Calculate Indegrees: Count how many incoming edges each node has.
Queue Zeroes: Find all nodes with 0 incoming edges (tasks with no prerequisites). Put them in a Queue.
Process:
- Dequeue a node and add it to the final sorted list.
- "Delete" the node from the graph (virtually).
- Decrement the indegree of all its neighbors.
- If a neighbor's indegree hits 0, add it to the Queue.
Repeat: Until the queue is empty.

Cycle Detection

If the queue empties but you haven't processed all nodes, it means there is a cycle (a deadlock). For example, A waits for B, and B waits for A.

Time ComplexityO(V + E)

We visit every node and every edge exactly once. It is extremely efficient.

Space ComplexityO(V)

We need an array to store indegrees and a queue for the zero-degree nodes.

Data StructureQueue + Indegree Array

The core data structure powering Kahn's Algorithm.

Visual PatternPeeling an onion. The outer layer (nodes with no dependencies) is stripped away, revealing new available nodes underneath.

How this algorithm appears during visualization.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1from collections import deque
2
3def kahn(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
4    """Topological sort using Kahn's algorithm (BFS-based).
5
6    Args:
7        n: Number of vertices (0 to n-1)
8        edges: List of (u, v) tuples meaning u -> v (u must come before v)
9
10    Returns:
11        List of vertices in topological order, or None if cycle detected
12    """
13    # Build adjacency list and compute indegrees
14    graph: list[list[int]] = [[] for _ in range(n)]
15    indegree: list[int] = [0] * n
16
17    for u, v in edges:
18        graph[u].append(v)
19        indegree[v] += 1
20
21    # Initialize queue with all nodes having indegree 0
22    # (nodes with no prerequisites)
23    queue: deque[int] = deque()
24    for node in range(n):
25        if indegree[node] == 0:
26            queue.append(node)
27
28    result: list[int] = []
29
30    while queue:
31        # Process node with no remaining dependencies
32        node = queue.popleft()
33        result.append(node)
34
35        # "Remove" this node by decrementing neighbor indegrees
36        for neighbor in graph[node]:
37            indegree[neighbor] -= 1
38
39            # If neighbor now has no dependencies, add to queue
40            if indegree[neighbor] == 0:
41                queue.append(neighbor)
42
43    # If we processed all nodes, we have a valid ordering
44    # Otherwise, there's a cycle
45    if len(result) == n:
46        return result
47    else:
48        return None  # Cycle detected