Breadth-First Search

Breadth-first search (BFS) explores a graph the way a ripple spreads on a pond: outward in rings, finishing everything one step from the start before touching anything two steps away. That discipline is its superpower — in an unweighted graph, the first time BFS reaches a node, it has arrived along a path with the fewest edges.

The queue is what keeps the order

BFS leans on a queue — a first-in, first-out line. You visit a node, push its unvisited neighbours onto the *back*, then pull the next node from the *front*. Because nearer nodes were enqueued earlier, they always come off first, so the search drains one full ring before the next begins. A visited set stops you from re-adding nodes and looping forever.

1. 1Put the start node in the queue and mark it visited with distance 0.
2. 2Dequeue the front node u.
3. 3For each neighbour v of u that isn't visited: mark it visited, set dist[v] = dist[u] + 1, and enqueue it at the back.
4. 4Repeat until the queue is empty — every reachable node has now been found in distance order.

function bfs(graph, start) {
  const dist = { [start]: 0 };
  const queue = [start];          // FIFO: push to back, shift from front
  while (queue.length) {
    const u = queue.shift();
    for (const v of graph[u]) {
      if (dist[v] === undefined) {  // not visited
        dist[v] = dist[u] + 1;
        queue.push(v);
      }
    }
  }
  return dist;                     // fewest-edges distance to every node
}