Depth-First Search

How DFS works

The recursive form is the natural one:

1. Start at the source node. Mark it visited.
2. For each unvisited neighbor, recursively DFS from it.
3. Return when all neighbors are processed.

That's it. The recursion stack tracks the current path. When you hit a dead end (all neighbors visited), the call returns and you backtrack to the previous node, automatically. The simplicity is why DFS is the default graph traversal in interview settings — the iterative-with-explicit-stack version produces the same output but takes 3× the code.

The iterative form swaps recursion for an explicit stack:

iterativeDFS(graph, start):
    stack = [start]
    visited = set()
    while stack not empty:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.push(neighbor)

Note: iterative DFS visits nodes in a slightly different order than recursive — pushing all neighbors before processing any reorders the traversal compared to recursing into them one at a time. The algorithm is still correct, just the visit order changes.

Three-color DFS for cycle detection

To detect cycles in a directed graph, mark each node with one of three states:

• White — not yet visited.
• Gray — currently on the recursion path (entered but not yet finished).
• Black — finished (entered, processed, returned).

If DFS encounters a gray neighbor, that's a back edge — there's a cycle from this node back to the gray ancestor. White and black transitions don't indicate cycles; only gray-on-gray does.

function hasCycle(graph) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Map();
  for (const node of Object.keys(graph)) color.set(node, WHITE);

  function dfs(node) {
    color.set(node, GRAY);
    for (const neighbor of graph[node] || []) {
      if (color.get(neighbor) === GRAY) return true;        // back edge → cycle
      if (color.get(neighbor) === WHITE && dfs(neighbor)) return true;
    }
    color.set(node, BLACK);
    return false;
  }

  for (const node of color.keys()) {
    if (color.get(node) === WHITE && dfs(node)) return true;
  }
  return false;
}

For undirected graphs, the rule is simpler: a back edge to any visited node (other than the immediate parent) indicates a cycle.

DFS vs BFS

	DFS	BFS
Strategy	Dive deep, backtrack	Expand level by level
Data structure	Stack (or recursion)	Queue
Memory on deep narrow graphs	High (depth ~ V)	Low (level ~ 1)
Memory on wide shallow graphs	Low (depth ~ 1)	High (level ~ V)
Shortest path (unweighted)	No guarantee	Yes — first reach is shortest
Cycle detection (directed)	Natural — three colors	Possible but awkward
Topological sort	Natural — finish order	Kahn's algorithm
Strongly connected components	Tarjan's, Kosaraju's	Not directly

When to use DFS

• Cycle detection. Three-color DFS is the standard algorithm.
• Topological sort. DFS in finish-time order, reverse for the topological ordering.
• Connected components. Run DFS from each unvisited node; each DFS call discovers exactly one component.
• Strongly connected components. Tarjan's and Kosaraju's algorithms are both DFS-based.
• Maze solving and backtracking. Dive into one path, hit a wall, back up, try the next. Recursive DFS makes the backtracking automatic.
• Tree algorithms. Pre/in/post-order traversal, lowest common ancestor, tree diameter, subtree-sum problems — all DFS.
• Memory-constrained graph search. When the graph is wide (high branching factor) but you suspect the target is near, DFS uses O(depth) memory while BFS uses O(width). For width ≫ depth, DFS wins.

JavaScript implementation

// Recursive — clearest expression of the algorithm
function dfs(graph, start, visited = new Set()) {
  if (visited.has(start)) return;
  visited.add(start);
  // process(start) — record / check goal / etc.
  for (const neighbor of graph[start] || []) {
    dfs(graph, neighbor, visited);
  }
  return visited;
}

// Iterative — works on graphs deep enough to overflow the call stack
function dfsIter(graph, start) {
  const visited = new Set();
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return visited;
}

// Topological sort using DFS finish order
function topoSort(graph) {
  const visited = new Set();
  const order = [];
  function visit(node) {
    if (visited.has(node)) return;
    visited.add(node);
    for (const neighbor of graph[node] || []) visit(neighbor);
    order.push(node); // push when finished — appears AFTER all descendants
  }
  for (const node of Object.keys(graph)) visit(node);
  return order.reverse(); // reverse finish order = topological order
}

Python implementation

def dfs(graph, start, visited=None):
    if visited is None: visited = set()
    if start in visited: return visited
    visited.add(start)
    for neighbor in graph.get(start, []):
        dfs(graph, neighbor, visited)
    return visited

# Iterative version — important when graph is too deep for recursion
def dfs_iter(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

import sys
sys.setrecursionlimit(100000)  # raise if needed for deep recursion

Famous DFS problems

Number of Islands

Given a 2D grid of 1s (land) and 0s (water), count the connected components of land. Run DFS from each unvisited land cell, marking everything reachable; each DFS call increments the count by 1.

function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  function sink(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited by mutating
    sink(r-1, c); sink(r+1, c); sink(r, c-1); sink(r, c+1);
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { count++; sink(r, c); }
  return count;
}

Common bugs and edge cases

• Stack overflow on deep graphs. Recursive DFS on 100k+ chain blows the call stack in most languages. Convert to iterative or raise the recursion limit.
• Marking visited too early or too late. Mark on entry to the recursive call, before exploring neighbors — otherwise duplicate work or infinite loops in cyclic graphs.
• Confusing forward edges with back edges in directed cycle detection. A forward edge to a visited (black) node is fine. A back edge to a node currently on the recursion path (gray) indicates a cycle. The three-color technique distinguishes them.
• Visiting the parent in undirected cycle detection. In undirected graphs, every edge appears twice (once from each side). When DFS sees a "visited" neighbor that's just the immediate parent, that's not a cycle — it's the same edge you arrived on. Pass the parent down and skip it.
• Using DFS to find shortest paths. DFS finds A path, not THE shortest. For shortest paths, use BFS (unweighted) or Dijkstra (weighted positive) or Bellman-Ford (any weights).