Topological sort
AlgorithmsMid priority~45 minLinearly order a DAG so every edge points forward — the tool for dependency resolution.
Definition
A topological sort orders the vertices of a directed acyclic graph so that every edge goes from earlier to later. Two standard methods: Kahn's algorithm (repeatedly remove a zero-in-degree node) and DFS post-order (reverse the finish order). If the graph has a cycle, no valid ordering exists. See Graphs for how this fits alongside BFS/DFS/Union-Find; this page walks both methods end to end.
When to use
Reach for it on dependency ordering — build systems, course prerequisites, task pipelines — and as a cycle-detection test on directed graphs (Kahn's leaves nodes unprocessed exactly when there's a cycle).
Techniques
Kahn's algorithm (BFS-flavored) — compute every node's in-degree, seed a queue with the nodes at in-degree 0 (no unmet dependencies), then repeatedly dequeue a node, append it to the result, and decrement its neighbours' in-degrees — enqueueing any that hit 0. If the result ends shorter than the full vertex count, some nodes never reached in-degree 0: a cycle.
DFS post-order — run DFS from every unvisited node; the instant a node's entire subtree is explored (its post-order moment), push it onto the front of the result (or push to the back and reverse at the end). A node's dependencies always finish exploring — and so get placed — before it does.
Kahn's is usually the more natural pick in an interview: it's iterative (no recursion-depth risk) and the cycle check falls out for free from comparing output length to vertex count, whereas DFS needs the separate three-color check from Depth-first search layered on top.
Related concepts
Kahn's algorithm is BFS with in-degree standing in for 'visited', and the DFS method is a direct extension of Depth-first search's three-color cycle check — a node only goes black once its whole subtree is done, which is exactly the moment it belongs at the front of the order. See Graphs for the full picture.
Implementation
function topologicalSort(numNodes, edges) {
const adj = Array.from({ length: numNodes }, () => []);
const inDegree = new Array(numNodes).fill(0);
for (const [from, to] of edges) {
adj[from].push(to);
inDegree[to]++;
}
let queue = [];
for (let node = 0; node < numNodes; node++) {
if (inDegree[node] === 0) queue.push(node); // no unmet dependencies — can go first
}
const order = [];
while (queue.length > 0) {
const next = [];
for (const node of queue) {
order.push(node);
for (const neighbor of adj[node]) {
if (--inDegree[neighbor] === 0) next.push(neighbor); // just lost its last dependency
}
}
queue = next;
}
return order; // order.length < numNodes ⇒ a cycle exists
}Worked examples
Course Schedule II — return a valid order to complete all courses given prerequisite pairs, or an empty array if it's impossible. Take numCourses = 4 with prerequisites [[1,0],[2,0],[3,1],[3,2]] (course 0 has no prerequisites; 1 and 2 each need 0; 3 needs both 1 and 2):
0 has no prerequisites; 3 needs both 1 and 2 finished first
Kahn's algorithm — the queue holds every course whose prerequisites are all satisfied
Only course 0 has no prerequisites, so it's the only node that starts in the queue.
Finishing 0 frees up both 1 and 2 — each loses its only prerequisite and joins the queue.
3 still needs 2 — its in-degree drops from 2 to 1, not yet enqueued.
Now 3 has no remaining prerequisites — it joins the queue.
All 4 courses are ordered — a valid schedule. Had any course been left with in-degree > 0, that would mean a cycle, and the answer would be [].
function findOrder(numCourses, prerequisites) {
const order = topologicalSort(
numCourses,
prerequisites.map(([course, prereq]) => [prereq, course]), // edge: prereq → course
);
return order.length === numCourses ? order : [];
}Building the adjacency list and in-degree array is O(V + E), and Kahn's loop visits every node and edge exactly once — also O(V + E) — for a total linear-time solution. Note that [0,1,2,3] isn't the only valid order here ([0,2,1,3] works too) — a DAG's topological order is rarely unique.
Things to look out for
- Forgetting to decrement a neighbour's in-degree when its prerequisite is dequeued leaves it permanently stuck out of the queue, even once it should be ready.
- The DFS method must place a node at the front of the result on completion (or reverse the array at the end) — pushing to the back on the way up gives the exact reverse of a valid order.
- Course Schedule (boolean 'can finish?') and Course Schedule II ('what order?') are the same traversal — don't rebuild the cycle check separately when Kahn's already gives you
order.length < numCoursesfor free.
Corner cases
- A single node with no edges — trivially sorted, order is just that one node.
- Several independent components — every component contributes its own nodes to the queue seed; don't assume one connected graph.
- A self-loop (a node depends on itself) — its in-degree never reaches 0, exactly like any other cycle.
- A DAG with independent branches has multiple valid topological orders — don't hardcode or assert one exact output; check the ordering constraints instead.
Practice
Essential
Recommended