Graph Depth-First Search

How It Works

Graph DFS explores a graph by picking a neighbor, going all the way down that branch until it can't go further, then backtracking to try the next neighbor. The universal skeleton is: mark the current node visited, then recurse into every unvisited neighbor.

function dfs(graph, node, visited) {
  if (visited.has(node)) return;
  visited.add(node);

  for (const neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
}

function countConnectedComponents(graph, nodes) {
  const visited = new Set();
  let components = 0;

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(graph, node, visited);
      components++;
    }
  }

  return components;
}

The representation of "neighbors" changes per problem — sometimes it's an adjacency list (graph[node] is an array of connected nodes), sometimes it's an adjacency matrix (isConnected[i][j] === 1), and sometimes it's implicit: a 2D grid where the "neighbors" of a cell are the cells directly above, below, left, and right of it. The traversal logic barely changes; only how you enumerate neighbors does.

When To Use It

Reach for graph DFS when you spot any of these signals:

• You need to count or label connected components — islands in a grid, provinces in a matrix, clusters in a social graph. DFS from every unvisited node and increment a counter each time you start a fresh traversal.
• The problem asks whether a cycle exists, most classically framed as "can you finish all courses given these prerequisites" — a cycle in the prerequisite graph means it's impossible.
• You need to visit every node reachable from a start point, marking them off as you go (flood fill, region marking).
• The input is a grid and adjacency is spatial (up/down/left/right) rather than an explicit edge list — grid-based DFS is one of the most common disguises for this pattern.
• You need to clone or deep-copy a graph, tracking already-visited/cloned nodes in a map to avoid infinite recursion on cycles.

If you instead need the shortest path or need to process nodes level-by-level, that's graph BFS, not DFS — DFS finds a path, not necessarily the shortest one.

Time & Space Complexity

• Time: O(V+E) — every vertex is visited once and every edge is examined once across the whole traversal (for grid problems, substitute "cells" for V and "cell-to-neighbor checks" for E, giving O(rows × cols)).
• Space: O(V) — the visited set plus the recursion call stack, which in the worst case (a graph that's one long chain) can be as deep as V, so watch out for stack overflows on very large inputs; an iterative DFS with an explicit stack avoids this.

Alternative Approaches

• Iterative DFS with an explicit stack: push the start node, pop, mark visited, push unvisited neighbors. Functionally equivalent to recursive DFS but avoids call-stack depth limits — prefer this for very large or deep graphs.
• Union-Find (Disjoint Set Union): for pure connected-component counting (no need to enumerate the actual path), union-find can be faster in practice and avoids recursion entirely, especially when components need to be merged incrementally as edges are added.
• BFS instead of DFS: for cycle detection specifically, Kahn's algorithm (BFS + in-degree tracking, i.e. topological sort) is a common non-recursive alternative to DFS-based cycle detection for course-schedule-style problems.

Common Mistakes

• Forgetting to mark a node visited before recursing into it — marking too late can cause infinite recursion on cyclic graphs.
• Not guarding grid boundaries — grid DFS needs explicit row >= 0 && row < rows && col >= 0 && col < cols checks before every recursive call, or you'll index out of bounds.
• Re-traversing already-visited nodes as new components — if you forget to check visited before starting a fresh DFS in the outer loop, you'll overcount components.
• Mutating the input grid without meaning to — a common trick is to flip visited land cells to '0' in place instead of using a separate visited set, which works but silently corrupts the input if the caller expected it unchanged.
• Missing the cycle-detection subtlety: a node can be "currently in the recursion stack" (gray) vs. "fully processed" (black) — checking only a single visited set (not distinguishing gray from black) will miss self-referencing-back-edge cycles in directed graphs like course schedules.

Pattern Summary

Graph DFS is "go deep, then backtrack," implemented as recurse-into-unvisited-neighbors with a visited set guarding against revisits and infinite loops. It's the right tool whenever you're counting components, detecting cycles, flood-filling a region, or copying a graph structure — anywhere you need to fully explore reachability rather than find the shortest route.