Graph DFS

How to think about it

Graph DFS is tree DFS with a visited set. Because a graph has no parent/child guarantees, you must mark a node before (or as) you recurse so you never revisit it. The whole skeleton is: mark, explore each unvisited neighbor, recurse. That is it. Almost every graph-DFS problem adds a layer on top of that invariant (count components, track a path, color bipartite, detect a back-edge).

Two representations dominate interview problems: an adjacency list (Map<V, V[]>) for general graphs, and a 2D grid (int[][] with 4-directional neighbors) for flood-fill / island problems. The template is identical; only the neighbor enumeration changes.

Template shapes

Shape	Core move	Example
Count components	if !visited: dfs(v); count++	LC 200, LC 547
Flood fill	Mutate cell, dfs 4-neighbors	LC 733, LC 695
Clone graph	Map<old, new>; dfs + copy on visit	LC 133
Pacific-Atlantic	Two DFS from borders, intersect reach	LC 417

Complexity baseline

O(V + E) time, every vertex and edge is considered once thanks to visited. Space O(V) for the visited set plus recursion depth (worst case O(V) on a path graph). For grid problems replace V with cells (RC) and E with 4R*C.

From template to problem

1. Choose the representation: adjacency list, grid, or implicit (e.g. words).
2. Decide what “visited” means, a boolean array, a set, or mutating the grid in place.
3. Identify the invariant each DFS call returns: a count, a boolean reach, a clone.
4. Loop over all starts; each unvisited start seeds one component / one fill.

/** Graph DFS template: count components + flood fill on a grid. */

export function countComponents(n: number, edges: [number, number][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let v = 0; v < n; v++) {
    if (!visited[v]) { dfs(v); count++; }
  }
  return count;

  function dfs(v: number) {
    visited[v] = true;
    for (const u of adj[v]) if (!visited[u]) dfs(u);
  }
}

export function floodFill(
  image: number[][], sr: number, sc: number, newColor: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === newColor) return image;
  const rows = image.length, cols = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= rows || c >= cols || image[r]![c] !== orig) continue;
    image[r]![c] = newColor;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

/** Graph DFS template: count components + flood fill on a grid. */

export function countComponents(n: number, edges: [number, number][]): number {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const visited = new Array<boolean>(n).fill(false);
  let count = 0;
  for (let v = 0; v < n; v++) {
    if (!visited[v]) { dfs(v); count++; }
  }
  return count;

  function dfs(v: number) {
    visited[v] = true;
    for (const u of adj[v]) if (!visited[u]) dfs(u);
  }
}

export function floodFill(
  image: number[][], sr: number, sc: number, newColor: number,
): number[][] {
  const orig = image[sr]![sc]!;
  if (orig === newColor) return image;
  const rows = image.length, cols = image[0]!.length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= rows || c >= cols || image[r]![c] !== orig) continue;
    image[r]![c] = newColor;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}