Breadth-First Search

How it works, step by step

1. 1

   Put the start node in a queue and mark it as seen, with distance 0.

2. 2

   Take the front node out of the queue.

3. 3

   Look at each of its neighbours. Every neighbour not seen before gets distance = current + 1, is marked seen, and joins the back of the queue.

4. 4

   A neighbour already seen is skipped - reaching it again cannot be shorter.

5. 5

   Repeat until the queue is empty. Nodes leave the queue in distance order: all the 1s, then the 2s, then the 3s...

6. 6

   Every node and edge is handled once - O(V + E) total.

The code, in JavaScript

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift();        // FRONT of the queue - that's BFS
    order.push(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next);             // mark when ENQUEUING, not later
        queue.push(next);
      }
    }
  }

  return order;
}

const graph = {
  A: ["B", "C", "H"], B: ["A", "D"], C: ["A", "D", "E"],
  H: ["A", "E"], D: ["B", "C", "G", "F"], E: ["C", "H", "F"],
  F: ["D", "E"], G: ["D"],
};

bfs(graph, "A");   // → ["A", "B", "C", "H", "D", "E", "G", "F"]

Dry run: BFS from node A

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Mark nodes as seen when you enqueue them, not when you dequeue. Marking late lets the same node enter the queue many times - on dense graphs that quietly turns O(V+E) into O(V²) or worse.
• `array.shift()` is O(n) in JavaScript - using it makes BFS itself O(V²) on big graphs. Use an index pointer (`queue[head++]`) or process ring-by-ring with two arrays.
• BFS's shortest-path guarantee dies the moment edges have weights. A 2-hop path of cost 1+1 beats a 1-hop edge of cost 10, but BFS picks the 1-hop. Weighted graphs need Dijkstra.
• The frontier can hold an entire level at once - on a wide graph (or a 1000×1000 grid) that is real memory, and it is the practical reason DFS sometimes wins despite BFS being "smarter".

Breadth-First Search vs. its closest relatives