Breadth-first search walks layers. Depth-first search walks a path as far as it goes, then unwinds. Same O(n + m) tax, different order, different theorems.
Use DFS when you care about reachability, connected components, back edges (cycles), or the order nodes finish. Use BFS when every edge costs the same and you want a shortest path. Mixing them up is the most common graph WA after 'forgot visited'.
function components(n, adj) {
const seen = Array(n).fill(false);
let count = 0;
function dfs(u) {
seen[u] = true;
for (const v of adj[u]) if (!seen[v]) dfs(v);
}
for (let u = 0; u < n; u++) {
if (seen[u]) continue;
count++;
dfs(u);
}
return count;
}Cycles. On a directed graph, a back edge to a node still on the recursion stack means a cycle. Three colors are the usual encoding: white = unseen, gray = on the stack, black = finished. Gray → gray is a cycle. Black is safe: that subgraph is already done.
On an undirected graph, every edge to the parent looks like a back edge if you are careless. Skip the parent; any other seen neighbor is a cycle.
If a directed graph has a cycle, it has no topological order. That is the next lesson, and the arena problem Course Schedule.
function hasCycle(n, adj) {
const color = Array(n).fill(0); // 0 white, 1 gray, 2 black
function dfs(u) {
color[u] = 1;
for (const v of adj[u]) {
if (color[v] === 1) return true; // back edge
if (color[v] === 0 && dfs(v)) return true;
}
color[u] = 2;
return false;
}
for (let u = 0; u < n; u++) {
if (color[u] === 0 && dfs(u)) return true;
}
return false;
}Checks 0/2