Graph Traversal: BFS and DFS

Model the state before the traversal

An adjacency list stores only existing edges. For an undirected connection, add both directions; for a dependency, preserve its direction. A grid can generate neighbors directly instead of materializing an adjacency list.

In a route-transfer problem, a bus route can be a vertex: boarding another route adds one to the answer. In obstacle elimination, reaching the same cell with more remaining eliminations is different from reaching it with none.

BFS: first discovery fixes the distance

The queue is ordered by nondecreasing distance. When a vertex is discovered from distance d, any shorter predecessor would already have been processed. Set its distance before enqueueing it, so two parents cannot schedule it twice.

function shortestDistances(neighbors, source) {
  const distance = new Array(neighbors.length).fill(-1);
  const queue = [source];
  distance[source] = 0;

  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    for (const next of neighbors[node]) {
      if (distance[next] !== -1) continue;
      distance[next] = distance[node] + 1;
      queue.push(next);
    }
  }
  return distance;
}

• The template expects an adjacency list and a valid source index. Unreachable vertices stay at -1.
• A head index avoids repeatedly removing the first array entry. The backing array retains discovered vertices, so this template uses O(V) queue storage.
• For multiple sources, enqueue all of them at distance zero before processing. Rotting Oranges uses this idea for simultaneous starting points.
• A parent array can reconstruct a shortest path; distances alone cannot.

DFS: schedule reachable work with a stack

The stack gives recently scheduled work priority. This template returns a reachability traversal, not a shortest path or a finish-time ordering. Marking on push prevents duplicate scheduling in cyclic graphs.

function reachableNodes(neighbors, source) {
  const seen = new Set([source]);
  const stack = [source];
  const order = [];

  while (stack.length) {
    const node = stack.pop();
    order.push(node);
    for (let i = neighbors[node].length - 1; i >= 0; i--) {
      const next = neighbors[node][i];
      if (seen.has(next)) continue;
      seen.add(next);
      stack.push(next);
    }
  }
  return order;
}

• Neighbor order can change the returned order without changing the reachable set.
• This mark-on-push stack need not produce the same DFS tree as recursive DFS. Low-link algorithms require explicit completion frames or recursive child returns.
• For all connected components in an undirected graph, start a traversal from each still-unvisited vertex, sharing the visited set.
• For directed cycle detection, distinguish active and finished vertices; one visited boolean is insufficient.

Trace the example, then change the invariant

Course Schedule and Foreign Dictionary add dependency ordering: Kahn's algorithm enqueues vertices whose indegree becomes zero. This is not the same queue invariant as shortest-distance BFS. Critical Connections instead tracks discovery and low-link values; neither basic template here is a bridge finder.

1. Start at 0 with distance 0 and queue [0].
2. Process 0: discover 1 and 2 at distance 1.
3. Process 1: discover 3 and 4 at distance 2. Process 2: discover 5 at distance 2.
4. The edge 4-5 finds an already discovered vertex, so it does not enqueue another copy. Distances are [0,1,1,2,2,2].

Complexity and failure modes

• With adjacency lists, each reachable vertex is processed once and each reachable adjacency entry once: O(V + E) worst-case time.
• Visited state, distances, and the explicit queue or stack use O(V) auxiliary space, excluding O(V + E) input storage.
• Scanning an adjacency matrix costs O(V) per processed vertex, so a full traversal can cost O(V squared).
• Backtracking is different: a visited state may need to be undone to explore another candidate. Do not reuse global reachability marking for Word Search.
• Weighted scores, such as maximizing a path's minimum cell, need a different ordering or threshold argument; do not apply ordinary BFS just because the input is a grid.

Mistakes and Counterexamples