Kahn's Algorithm: Topological Sort with BFS, Explained
Learn Kahn's algorithm for topological sort using BFS and in-degree counting — with a worked walkthrough, JavaScript code, complexity, and cycle detection.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Some things can only happen in a certain order. You install dependencies before you build. You take Calculus I before Calculus II. You pour the foundation before you frame the walls. Kahn's algorithm is how a computer finds a valid order for any such set of "this must come before that" rules — and, as a bonus, tells you when no valid order exists at all.
The structure underneath is a directed acyclic graph (DAG): nodes are tasks, and a directed edge u → v means u must come before v. The output is a topological sort — a linear ordering where every edge points forward. Kahn's approach builds that ordering the way you'd actually clear a to-do list: repeatedly do whatever has nothing blocking it, then cross off the dependencies it unblocks.
The problem
You're given n nodes labeled 0 to n-1 and a directed graph as an adjacency list, where graph[u] is the list of nodes that u points to. Return any valid topological ordering — a sequence where each node appears after every node that points into it. If the graph contains a cycle, no such ordering exists, so return an empty array.
Input: n = 4, graph = [[1, 2], [3], [3], []]
// 0 → 1, 0 → 2, 1 → 3, 2 → 3
Output: [0, 1, 2, 3] // 0 before 1 and 2; both before 3Read the edges as prerequisites: node 0 must be done before 1 and 2, and both 1 and 2 must be done before 3. [0, 1, 2, 3] respects all four edges. [0, 2, 1, 3] would be equally valid — a DAG can have many correct orderings, and you only need one.
The brute force baseline
The definition of a topological sort is "a node comes after everything pointing into it." So the naive idea is to repeatedly scan for a node whose prerequisites are all already placed, append it, and repeat.
function topoBrute(n, graph) {
const placed = new Set();
const order = [];
while (order.length < n) {
let progressed = false;
for (let node = 0; node < n; node++) {
if (placed.has(node)) continue;
// every predecessor of `node` already placed?
const ready = everyPredecessorPlaced(node, graph, placed);
if (ready) {
order.push(node);
placed.add(node);
progressed = true;
}
}
if (!progressed) return []; // stuck → cycle
}
return order;
}Each outer pass re-scans all n nodes, and checking whether a node is "ready" means examining edges again. In the worst case you place one node per full sweep, so you do on the order of O(n²) work plus repeated edge scans. Every pass re-asks a question you already answered on the previous pass. That repetition is the waste Kahn's algorithm removes.
The key insight: count what's blocking each node
Instead of re-checking readiness every pass, track it with a single number per node: the in-degree, the count of edges pointing into that node. A node is ready exactly when its in-degree hits 0 — nothing is blocking it anymore.
The reframe is a classic BFS layer peel:
- Compute every node's in-degree once.
- Every node with in-degree
0is a valid starting point — enqueue them all. - Pop a node, add it to the order, and "remove its outgoing edges" by decrementing each neighbor's in-degree. Any neighbor that drops to
0just became ready — enqueue it. - Repeat until the queue drains.
You never re-scan for ready nodes. A node announces itself the instant its last blocker is cleared. And the cycle check falls out for free: if you finish and haven't placed all n nodes, the leftovers form a cycle — they were each other's blockers, so none ever reached in-degree 0.
The optimal solution
This mirrors the exact code the visualizer steps through:
function topologicalSortBFS(n, graph) {
let indegree = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
for (let node of graph[i]) {
indegree[node]++;
}
}
let q = [];
let ans = [];
// Push indegree = 0 elements in queue
for (let i = 0; i < n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
while (q.length) {
let curr = q.shift();
ans.push(curr);
for (let neighbor of graph[curr]) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
if (ans.length != n) {
console.log("Graph has a cycle, and topo sort is not possible.");
return [];
}
return ans;
}Three phases, each doing linear work: build the in-degree array, seed the queue with the zero-in-degree nodes, then peel. The ans.length != n check at the end is the whole cycle detector — no separate pass, no visited-recursion-stack bookkeeping the way DFS-based topo sort needs.
Walkthrough
Trace n = 4, graph = [[1, 2], [3], [3], []]. After the counting loop, in-degrees are [0, 1, 1, 2]: node 0 has nothing pointing in, nodes 1 and 2 each have one incoming edge (from 0), and node 3 has two (from 1 and 2). Only node 0 starts at zero, so the queue seeds as [0].
| Step | Dequeue | Neighbors touched | in-degree after | Queue after | ans |
|---|---|---|---|---|---|
| seed | — | — | [0, 1, 1, 2] | [0] | [] |
| 1 | 0 | 1→0, 2→0 (both enqueue) | [0, 0, 0, 2] | [1, 2] | [0] |
| 2 | 1 | 3→1 (still blocked) | [0, 0, 0, 1] | [2] | [0, 1] |
| 3 | 2 | 3→0 (enqueue) | [0, 0, 0, 0] | [3] | [0, 1, 2] |
| 4 | 3 | none | [0, 0, 0, 0] | [] | [0, 1, 2, 3] |
Step 2 is the instructive one: dequeuing 1 decrements node 3's in-degree from 2 to 1, but 1 ≠ 0, so 3 stays out of the queue. Node 3 has two prerequisites and only one is cleared. It's not until step 3, when node 2 clears the second edge, that 3 drops to 0 and finally enqueues. The queue empties with ans holding all four nodes, so ans.length === n — a valid ordering, no cycle.
If the graph had been [[1], [2], [0]] (a 0 → 1 → 2 → 0 loop), every node would start with in-degree 1, the seed queue would be empty, the while loop would never run, and ans would stay [] — length 0 ≠ 3, correctly flagged as a cycle.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(V + E) | Each node is enqueued/dequeued once (V); each edge is relaxed once when its source is processed (E). |
| Space | O(V + E) | O(V) for the in-degree array plus the queue; the adjacency list itself holds the E edges. |
Compared to the O(n²) brute force, the in-degree array is what buys the speedup: readiness becomes an O(1) counter update instead of a repeated scan. Every edge is looked at exactly once, in the moment its source node is dequeued.
Common mistakes
- Counting out-degree instead of in-degree. You want incoming edges. The loop is
for (node of graph[i]) indegree[node]++— you increment the target's count, not the source's. - Seeding the queue before counting is finished. Compute all in-degrees first, then scan for zeros. Interleaving the two loops enqueues nodes whose counts aren't final yet.
- Forgetting the
ans.length != ncheck. Without it, a cyclic graph silently returns a partial ordering that looks valid but isn't. That final length comparison is the entire cycle detector — don't drop it. - Using an array with
shift()and expecting O(1) dequeue.Array.prototype.shift()is O(n). For large graphs, use a head-pointer index or a real deque so the queue stays O(1) per operation. - Assuming the output is unique. DAGs with independent branches have multiple valid orders. If a checker expects one specific ordering, you may need a tie-break rule (e.g. a min-heap instead of a plain queue for lexicographically smallest).
Where this pattern shows up next
In-degree peeling and directed-graph traversal underpin a whole family of problems:
- Redundant Connection — the cycle-detection cousin, solved with union-find on an undirected graph.
- Find if Path Exists in Graph — reachability, the simplest form of "does an ordering-style traversal connect these two?"
- All Paths From Source to Target — enumerating every route through a DAG, where a topological mindset keeps the search acyclic.
- Max Area of Island — BFS/DFS flood fill, the traversal engine that Kahn's queue is a directed specialization of.
You can also step through Kahn's algorithm interactively to watch the in-degree array drain and the queue peel one layer at a time.
FAQ
What is the difference between Kahn's algorithm and DFS topological sort?
Both produce a valid topological ordering in O(V + E), but they get there differently. Kahn's is BFS-based: it tracks in-degrees and repeatedly removes nodes with zero incoming edges, building the order front to back. DFS-based topo sort recurses to the deepest nodes first and prepends each node to the order as its recursion returns, building the order back to front. Kahn's tends to be easier to reason about for cycle detection and avoids recursion depth limits on very deep graphs.
How does Kahn's algorithm detect a cycle?
By counting. In a cycle, every node has at least one incoming edge from another node in that cycle, so none of them can ever reach in-degree 0. They never enter the queue and never get processed. After the loop drains the queue, you compare ans.length to n: if fewer than n nodes were placed, the unprocessed ones form a cycle and no valid ordering exists. The algorithm returns an empty array in that case.
Why use in-degree instead of just checking prerequisites each time?
The in-degree is a running count that turns an expensive question — "are all of this node's prerequisites done?" — into a single O(1) comparison against zero. Without it, you'd re-scan every node's incoming edges on every pass, which is the O(n²)-plus brute force. Decrementing a counter when you remove an edge means each node announces its own readiness the instant its last blocker clears, so you never re-check.
Can a topological sort have more than one valid answer?
Yes. Whenever two or more nodes sit at in-degree 0 at the same time, you can process them in any order, so a DAG with independent branches has multiple correct topological orderings. For [[1, 2], [3], [3], []], both [0, 1, 2, 3] and [0, 2, 1, 3] are valid. If a problem demands a specific one — say, lexicographically smallest — swap the plain queue for a min-heap so you always pop the smallest ready node.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.