Pattern Reference
Topological Sort
"Kahn's algorithm, DFS-based sort, course schedule, dependency resolution."
Loading...
Deep Dive Tutorial
Topological sort only works on DAGs (directed acyclic graphs). The key insight: a node can be processed once all its prerequisites are done. Kahn's algorithm uses in-degree counting — start with all nodes that have no dependencies, process them, reduce neighbors' in-degrees, add new zero-in-degree nodes. If any nodes remain after BFS, there's a cycle.
Both topological sort algorithms
// Kahn's Algorithm (BFS) — detects cycles, gives one valid order
function topoSortKahn(n, edges) {
const graph = Array.from({length: n}, () => []);
const inDegree = new Array(n).fill(0);
for (const [u, v] of edges) {
graph[u].push(v);
inDegree[v]++;
}
const queue = [];
for (let i = 0; i < n; i++) if (inDegree[i] === 0) queue.push(i);
const order = [];
let i = 0;
while (i < queue.length) {
const node = queue[i++];
order.push(node);
for (const nei of graph[node]) {
if (--inDegree[nei] === 0) queue.push(nei);
}
}
return order.length === n ? order : []; // empty = cycle detected
}
// DFS Post-order — append to stack after visiting all descendants
function topoSortDFS(n, edges) {
const graph = Array.from({length: n}, () => []);
for (const [u, v] of edges) graph[u].push(v);
const visited = new Array(n).fill(0); // 0=unvisited, 1=in-stack, 2=done
const stack = [];
let hasCycle = false;
function dfs(node) {
if (visited[node] === 1) { hasCycle = true; return; }
if (visited[node] === 2) return;
visited[node] = 1;
for (const nei of graph[node]) dfs(nei);
visited[node] = 2;
stack.push(node);
}
for (let i = 0; i < n; i++) dfs(i);
return hasCycle ? [] : stack.reverse();
}Worked Problems
triangle
Kahn's vs DFS topo sort:
- Kahn's: iterative, naturally counts "layers" (parallel courses, levels), easier cycle detection (count processed = n?)
- DFS post-order: recursive, good when you also need DFS tree info
Cycle detection: Kahn's — if processed count < n, cycle. DFS — if you revisit an in-progress node.
Applications pattern:
- "Can all tasks complete?" → topo sort, check for cycle
- "In what order?" → return topo order
- "How many steps/levels?" → count BFS layers in Kahn's
- "Longest chain?" → DP on topo order: dp[node] = 1 + max(dp[prerequisites])
- Kahn's: iterative, naturally counts "layers" (parallel courses, levels), easier cycle detection (count processed = n?)
- DFS post-order: recursive, good when you also need DFS tree info
Cycle detection: Kahn's — if processed count < n, cycle. DFS — if you revisit an in-progress node.
Applications pattern:
- "Can all tasks complete?" → topo sort, check for cycle
- "In what order?" → return topo order
- "How many steps/levels?" → count BFS layers in Kahn's
- "Longest chain?" → DP on topo order: dp[node] = 1 + max(dp[prerequisites])