Graph Traversal (BFS & DFS)

Traversing a graph is like traversing a tree — with one dangerous difference: graphs have cycles. Follow edges naively and you can loop forever, or revisit the same node again and again. The fix is a single idea that appears in every graph algorithm: a visited set that records where you have already been.

Once you guard against revisiting, the same two strategies from trees carry over. Breadth-first search (BFS) spreads outward in rings using a queue, so the first time it reaches a node is along the fewest edges — that makes it the shortest-path algorithm on an unweighted graph. Depth-first search (DFS) plunges down one path using a stack (or recursion), which is perfect for reachability and connectivity questions.

BFS — shortest hops in an unweighted graph

BFS processes nodes in order of distance from the source. Mark a node visited when you enqueue it (not when you dequeue it) so it never lands in the queue twice.

function bfsDistances(graph, start) {
  const dist = new Map([[start, 0]])
  const queue = [start]
  while (queue.length) {
    const node = queue.shift()
    for (const next of graph[node]) {
      if (!dist.has(next)) {          // first time seen = shortest
        dist.set(next, dist.get(node) + 1)
        queue.push(next)
      }
    }
  }
  return dist                          // node -> hops from start
}

DFS — recursion or an explicit stack

DFS commits to one neighbour and follows it as deep as possible before backtracking. The recursive form is the shortest; the iterative form swaps the call stack for an explicit one, which avoids stack-overflow on huge graphs.

function dfsRecursive(graph, node, visited = new Set()) {
  visited.add(node)
  for (const next of graph[node]) {
    if (!visited.has(next)) dfsRecursive(graph, next, visited)
  }
  return visited
}

function dfsIterative(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 next of graph[node]) {
      if (!visited.has(next)) stack.push(next)
    }
  }
  return visited
}

Grids are graphs in disguise

A 2D grid is just an implicit graph: each cell is a node, and its neighbours are the (up to) four cells around it. Instead of an adjacency list you compute neighbours on the fly with direction offsets. This is the backbone of flood-fill, island-counting, and maze problems.

function bfsGrid(grid, sr, sc) {
  const rows = grid.length, cols = grid[0].length
  const seen = new Set([sr + ',' + sc])
  const queue = [[sr, sc]]
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  while (queue.length) {
    const [r, c] = queue.shift()
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc
      const key = nr + ',' + nc
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue
      if (grid[nr][nc] === 0 || seen.has(key)) continue   // 0 = wall
      seen.add(key)
      queue.push([nr, nc])
    }
  }
  return seen
}

Connected components

A disconnected graph splits into islands of mutually reachable nodes. Loop over every node; whenever you find one that has not been visited, launch a fresh BFS/DFS from it — each launch discovers exactly one component. Counting the launches counts the components.

• Use BFS when you need the shortest path in hops, level-by-level order, or the minimum number of steps.
• Use DFS for reachability, cycle detection, topological sort, and exploring all paths.
• Either one finds connected components — pick by whichever guard (queue vs stack/recursion) fits the problem.
• Always mark visited the moment a node enters the frontier, or a cycle will trap you in an infinite loop.