Depth-first search

Overview

Depth-first search (DFS) explores a graph by going as deep as possible along one path before backtracking. It uses a stack, either the call stack through recursion or an explicit one, and a visited set so each node is processed once.

DFS is the natural tool for exploring everything reachable: counting connected components, flood-filling regions, detecting cycles, topological ordering, and generating all paths. Unlike BFS it does not find shortest paths, but it uses memory proportional to depth rather than width and is usually shorter to write.

When to use it

• Explore all nodes reachable from a start: islands, provinces, regions.
• Detect cycles in directed or undirected graphs.
• Topological sort of a DAG (postorder).
• Enumerate all paths or configurations (backtracking is DFS on a decision tree).
• Tree problems, which are DFS on a special graph.

Problem patterns it solves

Where it is used in real software

Key terms

Visited set

Prevents revisiting nodes and infinite loops in cyclic graphs.

Backtracking

Returning to the previous node when all neighbors are explored.

Three colors

0 = unvisited, 1 = in the current path, 2 = finished. A 1 -> 1 edge means a directed cycle.

Discovery / finish time

When a node is first reached and when its exploration completes.

Back edge

An edge to an ancestor in the current DFS path, which indicates a cycle.

How it works, step by step

1. 1
   Mark the node visited

   Do this before exploring neighbors.

2. 2
   Process the node (preorder work)

   Count it, color it, or add it to a path.

3. 3
   Recurse into each unvisited neighbor

   Go deep before trying the next neighbor.

4. 4
   Finish the node (postorder work)

   Mark it done, add it to a topological order, or remove it from the current path.

5. 5
   Repeat from every unvisited node

   This handles disconnected graphs and counts components.

Number of islands

grid = ["11000", "11000", "00100", "00011"]

3 islands. Each DFS marks its whole island as visited, so every cell is processed a constant number of times: O(rows x cols).

Implementation

1function numIslands(grid) {2  const rows = grid.length, cols = grid[0].length;3  let count = 0;4  function sink(r, c) {5    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== "1") return;6    grid[r][c] = "0"; // mark visited7    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);8  }9  for (let r = 0; r < rows; r++) {10    for (let c = 0; c < cols; c++) {11      if (grid[r][c] === "1") {12        count++;13        sink(r, c);14      }15    }16  }17  return count;18}19 20// Iterative DFS avoids recursion limits on big graphs21function reachable(graph, start) {22  const visited = new Set([start]);23  const stack = [start];24  while (stack.length) {25    const node = stack.pop();26    for (const next of graph[node]) {27      if (!visited.has(next)) {28        visited.add(next);29        stack.push(next);30      }31    }32  }33  return visited;34}35 36// Directed cycle detection with three colors37function canFinish(numCourses, prerequisites) {38  const graph = Array.from({ length: numCourses }, () => []);39  for (const [course, pre] of prerequisites) graph[pre].push(course);40  const state = new Array(numCourses).fill(0); // 0 new, 1 visiting, 2 done41  function hasCycle(u) {42    if (state[u] === 1) return true;  // back edge43    if (state[u] === 2) return false;44    state[u] = 1;45    for (const v of graph[u]) if (hasCycle(v)) return true;46    state[u] = 2;47    return false;48  }49  for (let i = 0; i < numCourses; i++) if (hasCycle(i)) return false;50  return true;51}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Marking visited after the recursive call.

  Fix: Mark before exploring neighbors, or cycles cause infinite recursion.

• Using a visited set for directed cycle detection.

  Fix: A single visited set cannot tell the current path from finished nodes; use three states.

• Starting DFS from only one node.

  Fix: Loop over all nodes to cover disconnected components.

• Forgetting to copy the path when saving results.

  Fix: Push a copy (new ArrayList<>(path), [...path]), not the mutable list.

Interview questions

Practice problems