1. Count prerequisites
Each incoming edge is one prerequisite for the target node.
indegree[next] += 1Typorithm · medium
Topological Sort
▷ Interactive algorithm labtopological-sortgraph-algorithmsindegreekahndag
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Topological Sort
Graph Algorithms
Kahn's algorithm: repeatedly emit nodes with zero remaining prerequisites using an indegree count.
A topological order lists nodes so every edge points from earlier to later — only possible on a DAG.
Count each node's indegree, start with the zero-indegree nodes, and emit them one by one.
Emitting a node decrements its neighbors' indegrees; new zeros join the queue.
Preparing algorithm lab…
01
Indegree = number of prerequisites.
02
Emit zero-indegree nodes first.
03
Leftover nodes mean a cycle.
function topoSort(graph, n) {
const indegree = new Array(n).fill(0);
for (let node = 0; node < n; node += 1) {
for (const next of graph[node]) {
indegree[next] += 1;
}
}
const queue = [];
for (let node = 0; node < n; node += 1) {
if (indegree[node] === 0) queue.push(node);
}
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const next of graph[node]) {
indegree[next] -= 1;
if (indegree[next] === 0) queue.push(next);
}
}
return order.length === n ? order : [];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Seed zero-indegree
Nodes with no prerequisites can go first.
if (indegree[node] === 0) queue.push(node)3. Emit node
A dequeued node has all prerequisites satisfied.
order.push(node)4. Drop prerequisite
Removing a node satisfies one prerequisite of each neighbor.
indegree[next] -= 15. Cycle check
If not all nodes emit, a cycle made a valid order impossible.
return order.length === n ? order : []A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.