Lesson 24
Depth-First Search & Topological Sort
Go deep, backtrack, and order tasks so every dependency comes first.
01Why it matters & the intuition
DFS detects cycles, finds connected components and powers topological sort — the algorithm behind build systems, package managers (npm install order!) and course prerequisites.
Think of it like…
Exploring a maze with a ball of string: follow one corridor as far as it goes, and when you hit a dead end, wind the string back to the last junction and try the next corridor.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- discovered / in container
- processing now
- finished
03Key ideas
DFS with recursion or a stack
Visit a node, then recursively visit each unvisited neighbour. The call stack remembers where to backtrack to.
Three colours
White = unvisited, grey = on the current path, black = finished. Meeting a grey node in a directed graph means a cycle.
Topological order
For a DAG, list nodes so every edge points forward. Reverse post-order of DFS gives one; so does Kahn's algorithm.
Kahn's algorithm
Count incoming edges (in-degree). Repeatedly take a node with in-degree 0 and decrement its neighbours. If nodes remain, there is a cycle.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
// Kahn's algorithm — returns an order, or null if a cycle exists.
function topoSort(n: number, edges: [number, number][]): number[] | null {
const adj: number[][] = Array.from({ length: n }, () => []);
const indegree = new Array(n).fill(0);
for (const [from, to] of edges) { adj[from].push(to); indegree[to]++; }
const queue: number[] = [];
for (let v = 0; v < n; v++) if (indegree[v] === 0) queue.push(v);
const order: number[] = [];
for (let h = 0; h < queue.length; h++) {
const v = queue[h];
order.push(v);
for (const w of adj[v]) if (--indegree[w] === 0) queue.push(w);
}
return order.length === n ? order : null;
}
// Recursive DFS collecting nodes in visitation order.
function dfs(adj: number[][], start: number, seen = new Set<number>(), out: number[] = []): number[] {
seen.add(start);
out.push(start);
for (const next of adj[start]) if (!seen.has(next)) dfs(adj, next, seen, out);
return out;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| DFS | O(V + E) | O(V) |
| Topological sort (Kahn / DFS) | O(V + E) | — |
| Cycle detection | O(V + E) | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Course schedule
Write can_finish(numCourses, prerequisites) where each pair [a, b] means course b must be taken before a. Return true if all courses can be completed (i.e. no cycle).