patternjavascriptModerate

BFS with a queue finds shortest path in unweighted graphs

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

bfsbreadth first searchqueueshortest pathgraph traversallevel order

Problem

DFS is simpler to write recursively, so developers default to it even when BFS is needed. BFS is necessary for shortest path in unweighted graphs — DFS gives A path, not THE shortest path.

Solution

BFS uses a queue (FIFO). Enqueue the start node, mark visited, then loop: dequeue, process, enqueue unvisited neighbors. Distance is implicit in BFS levels — use a distance Map or encode level in the queue entries.

Why

BFS explores nodes layer by layer in order of distance from the source. The first time BFS reaches a node is via the shortest path. DFS may reach it via a longer path first.

Gotchas

Mark nodes visited WHEN enqueuing, not when dequeuing — marking on dequeue allows the same node to be enqueued multiple times
Use a proper queue (or simulate with an index pointer) — Array.shift() is O(n) and kills performance for large graphs
BFS on a grid: treat each cell as a node with up to 4 neighbors

Code Snippets

BFS with distance tracking, no O(n) shift

function bfs(graph, start) {
  const visited = new Set([start]);
  const dist = new Map([[start, 0]]);
  const queue = [start];
  let head = 0; // avoid O(n) shift

  while (head < queue.length) {
    const node = queue[head++];
    for (const neighbor of (graph.get(node) ?? [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dist.set(neighbor, dist.get(node) + 1);
        queue.push(neighbor);
      }
    }
  }
  return dist;
}

Context

Finding shortest paths, level-order traversal, or reachability in unweighted graphs

Revisions (0)

No revisions yet.