Topological sort of a DAG
Problem
Given a directed acyclic graph (n nodes, with edges u → v meaning u must come before v), return any ordering of the nodes in which every edge points forward. In Course Schedule II the edges are prerequisites; return [] if a cycle makes an ordering impossible.
Example 1
Input: n = 4, edges = [[1,0], [2,0], [3,1], [3,2]] (course, prerequisite) Output: [0, 1, 2, 3] or [0, 2, 1, 3]
Also asked as: topological sort · course schedule
Test cases
Case 1
Input: 4, [[0,1],[0,2],[1,3],[2,3]] Expected (any of): [[0,1,2,3],[0,2,1,3]]
Case 2
Input: 2, [[0,1],[1,0]] Expected (any of): [null,[]]
Case 3
Input: 1, [] Expected (any of): [[0]]
View solutionHide solution2 approaches
1. Kahn's algorithm (BFS on in-degrees)
Time O(V + E)Space O(V + E)
Repeatedly remove a node with in-degree 0 and decrement its neighbours. If you can’t process all nodes, there is a cycle.
function topoSort(numNodes, edges) { const adj = Array.from({ length: numNodes }, () => []); const indeg = Array(numNodes).fill(0); for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; } const q = []; for (let i = 0; i < numNodes; i++) if (indeg[i] === 0) q.push(i); const order = []; while (q.length) { const u = q.shift(); order.push(u); for (const v of adj[u]) if (--indeg[v] === 0) q.push(v); } return order.length === numNodes ? order : null; // null ⇒ cycle}2. DFS with colours
Time O(V + E)Space O(V + E)
DFS; push a node to the front of the order after its subtree is done. A back-edge to a "grey" node means a cycle.
function topoSort(numNodes, edges) { const adj = Array.from({ length: numNodes }, () => []); for (const [u, v] of edges) adj[u].push(v); const state = Array(numNodes).fill(0); // 0=unseen 1=in-progress 2=done const order = []; let ok = true; const dfs = (u) => { state[u] = 1; for (const v of adj[u]) { if (state[v] === 1) { ok = false; return; } if (state[v] === 0) dfs(v); } state[u] = 2; order.push(u); }; for (let i = 0; i < numNodes && ok; i++) if (state[i] === 0) dfs(i); return ok ? order.reverse() : null;}