Breadth-First Search: The Wave That Finds the Shortest Path

Introduction

Drop a stone in a pond and the ripple reaches every point at distance 1 before any point at distance 2. Breadth-first search (BFS) does exactly that to a graph. Starting from a source vertex $s$ , it first visits every neighbour of $s$ , then every vertex two edges away, then three, and so on — one complete layer at a time.

The whole trick is the data structure. BFS keeps its frontier in a FIFO queue (first in, first out): vertices are served in the order they were discovered, so nobody from layer $k+1$ can jump ahead of someone from layer $k$ . Swap the queue for a stack and you get depth-first search, which dives down one corridor as far as it can before backing up — a perfectly good way to explore, but a terrible way to find short routes.

BFS(G, s):
    for each vertex v:  dist[v] ← ∞ ; parent[v] ← nil
    dist[s] ← 0
    Q ← empty queue ; enqueue(Q, s)
    while Q is not empty:
        u ← dequeue(Q)
        for each neighbour v of u:
            if dist[v] = ∞:            # first time we see v
                dist[v] ← dist[u] + 1
                parent[v] ← u
                enqueue(Q, v)

When the loop ends, dist[v] is the number of edges on a shortest path from $s$ to $v$ (or $\infty$ if $v$ is unreachable), and following parent pointers back from $v$ spells out such a path. The parent pointers together form the BFS tree: a shortest-path tree rooted at $s$ .

A short history. BFS was invented more than once. Konrad Zuse described it in 1945, in his rejected doctoral thesis on the Plankalkül programming language, to find the connected components of a graph — but that work was not published until 1972. Edward F. Moore reinvented it in 1959 to find the shortest path out of a maze, and C. Y. Lee independently developed it in 1961 for routing wires on circuit boards; on grids it is still called the Lee algorithm.

Try It

Below is a 15 × 11 maze. S is the start, the purple corner is the goal. Click any cell to add or remove a wall, then press Step to process one cell at a time or Run to watch the whole search. The yellow cells are the current frontier — exactly the contents of the queue listed under the grid.

<p class="hint">Breadth-first search spreads from the start <b>S</b> like a wave, one layer at a time. Each explored cell shows its distance from S. Click cells to add or remove walls, then press <b>Step</b> or <b>Run</b>. Switch to DFS to see why a stack does not find the shortest path.</p>
<div class="bar">
  <label for="mode">Algorithm:</label>
  <select id="mode">
    <option value="bfs">BFS (queue)</option>
    <option value="dfs">DFS (stack)</option>
  </select>
</div>
<div id="grid" class="grid" role="grid" aria-label="Maze grid; click a cell to toggle a wall"></div>
<div class="stats">
  <span>Explored: <b id="nVisited">0</b></span>
  <span id="lblFront">In queue:</span> <b id="nFront">1</b>
  <span>Path length: <b id="nPath">–</b></span>
</div>
<div class="status" id="status">Edit the walls, then press Step or Run.</div>
<div class="queue">
  <div class="qtitle" id="qtitle">Queue, front → back: (x,y) distance</div>
  <div id="qitems" class="qitems"></div>
</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">Reset</button>
  <button id="maze" type="button" class="ghost">Random maze</button>
  <button id="clear" type="button" class="ghost">Clear walls</button>
</div>
<div class="legend">
  <span><i class="sw start"></i>Start</span>
  <span><i class="sw goal"></i>Goal</span>
  <span><i class="sw wall"></i>Wall</span>
  <span><i class="sw front"></i>Frontier</span>
  <span><i class="sw path"></i>Path found</span>
</div>

/* Colour palette as variables, with a dark-mode variant. */
:root { --fg: #1f2933; --muted: #52606d; --bg: #ffffff; --cell: #eef2f6; --wall: #2f3e4e;
        --accent: #1d3557; --front: #ffd166; --path: #e63946; --start: #2a9d8f; --goal: #7b2cbf; }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e4e9ef; --muted: #a7b4c2; --bg: #14181d; --cell: #232a33; --wall: #8a9aac;
          --accent: #74b3ce; --front: #c9a227; --path: #ff6b6b; --start: #3cc1b1; --goal: #b47ce8; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; }
.hint { font-size: .88rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.45; }
.bar { display: flex; align-items: center; gap: .5rem; margin-bottom: .45rem; font-size: .9rem; }
select { font: 600 13px system-ui, sans-serif; padding: .25rem .4rem; border-radius: 6px;
         border: 1px solid var(--accent); background: var(--bg); color: var(--fg); }
.grid { display: grid; grid-template-columns: repeat(15, 1fr); gap: 1px; width: 100%; max-width: 465px;
        background: var(--muted); border: 1px solid var(--muted); user-select: none; touch-action: manipulation; }
.cell { aspect-ratio: 1 / 1; background: var(--cell); display: flex; align-items: center; justify-content: center;
        font: 600 clamp(8px, 2.4vw, 11px) ui-monospace, monospace; color: #1f2933; cursor: pointer; overflow: hidden;
        transition: background-color .18s; }
.cell.wall { background: var(--wall); }
.cell.front { background: var(--front) !important; }
.cell.cur { outline: 2px solid var(--accent); outline-offset: -2px; }
.cell.path { background: var(--path) !important; color: #fff; }
.cell.start { background: var(--start) !important; color: #fff; }
.cell.goal { background: var(--goal) !important; color: #fff; }
.stats { display: flex; flex-wrap: wrap; gap: .3rem .9rem; font-size: .88rem; margin: .5rem 0 .2rem; }
.status { font-size: .92rem; font-weight: 600; min-height: 2.6em; margin: .25rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
@media (prefers-color-scheme: dark) { .status.ok { color: #5fd38d; } .status.bad { color: #ff8a8a; } }
.queue { font-size: .8rem; margin-bottom: .5rem; }
.qtitle { color: var(--muted); margin-bottom: .2rem; }
.qitems { display: flex; flex-wrap: wrap; gap: 3px; min-height: 1.4em; }
.qitems span { font: 12px ui-monospace, monospace; padding: 1px 5px; border-radius: 4px; background: var(--front); color: #1f2933; }
.qitems span.more { background: transparent; color: var(--muted); }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid var(--accent);
         background: var(--accent); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: var(--bg); color: var(--accent); }
.legend { display: flex; flex-wrap: wrap; gap: .3rem .8rem; font-size: .78rem; color: var(--muted); margin-top: .55rem; }
.sw { display: inline-block; width: 11px; height: 11px; border-radius: 2px; margin-right: 4px; vertical-align: -1px; }
.sw.start { background: var(--start); } .sw.goal { background: var(--goal); } .sw.wall { background: var(--wall); }
.sw.front { background: var(--front); } .sw.path { background: var(--path); }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const W = 15, H = 11, N = W * H;
const START = 0, GOAL = N - 1; // start at the top-left corner, goal at the bottom-right

// Small seeded random generator, so the first maze is always the same.
function mulberry32(a) { return function () { a |= 0; a = a + 0x6D2B79F5 | 0;
  let t = Math.imul(a ^ a >>> 15, 1 | a); t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
  return ((t ^ t >>> 14) >>> 0) / 4294967296; }; }

// Carve a perfect maze with a randomized depth-first walk on the even cells,
// then knock out extra walls so the maze has loops (and several possible routes).
function makeMaze(rnd) {
  const walls = new Array(N).fill(true);
  walls[START] = false;
  const stack = [START];
  while (stack.length) {
    const u = stack[stack.length - 1], r = Math.floor(u / W), c = u % W, opts = [];
    for (const [dr, dc] of [[-2, 0], [0, 2], [2, 0], [0, -2]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < H && nc >= 0 && nc < W && walls[nr * W + nc]) opts.push([nr, nc]);
    }
    if (!opts.length) { stack.pop(); continue; }
    const [nr, nc] = opts[Math.floor(rnd() * opts.length)];
    walls[((r + nr) / 2) * W + (c + nc) / 2] = false;
    walls[nr * W + nc] = false;
    stack.push(nr * W + nc);
  }
  // Open some walls between corridors to create cycles.
  for (let i = 0; i < N; i++) {
    const r = Math.floor(i / W), c = i % W;
    if (walls[i] && (r % 2) + (c % 2) === 1 && rnd() < 0.25) walls[i] = false;
  }
  return walls;
}

// Open neighbours of cell i in the order up, right, down, left.
function neighbors(i, walls) {
  const r = Math.floor(i / W), c = i % W, out = [];
  if (r > 0) out.push(i - W);
  if (c < W - 1) out.push(i + 1);
  if (r < H - 1) out.push(i + W);
  if (c > 0) out.push(i - 1);
  return out.filter((j) => !walls[j]);
}

// Search state: dist = layer number (-1 = unseen), parent pointers, explored flags, frontier.
function newSearch(mode) {
  const s = { mode, dist: new Array(N).fill(-1), parent: new Array(N).fill(-1), done: new Array(N).fill(false),
              frontier: [START], finished: false, found: false, visited: 0, current: -1 };
  s.dist[START] = 0;
  return s;
}

// One step: take a cell from the frontier (front of the queue for BFS, top of the stack for DFS),
// mark it explored and add its unseen neighbours with distance + 1.
function step(s, walls) {
  if (s.finished) return;
  if (s.mode === 'dfs') while (s.frontier.length && s.done[s.frontier[s.frontier.length - 1]]) s.frontier.pop();
  if (!s.frontier.length) { s.finished = true; return; }
  const u = s.mode === 'bfs' ? s.frontier.shift() : s.frontier.pop();
  s.done[u] = true; s.visited++; s.current = u;
  if (u === GOAL) { s.finished = true; s.found = true; return; }
  const nb = neighbors(u, walls);
  if (s.mode === 'dfs') nb.reverse(); // so the stack pops neighbours in the same up/right/down/left order
  for (const v of nb) {
    if (s.mode === 'bfs' ? s.dist[v] < 0 : !s.done[v]) {
      s.dist[v] = s.dist[u] + 1; s.parent[v] = u; s.frontier.push(v);
    }
  }
}

// Follow parent pointers back from the goal to rebuild the path.
function pathTo(s, t) { const p = []; if (s.dist[t] < 0) return p; for (let v = t; v !== -1; v = s.parent[v]) p.push(v); return p.reverse(); }

// Plain BFS to the end, used to compare the DFS path with the true shortest path.
function shortest(walls) {
  const s = newSearch('bfs');
  while (!s.finished) step(s, walls);
  return s.found ? s.dist[GOAL] : -1;
}

// Drawing and buttons.
const $ = (id) => document.getElementById(id);
const dark = window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches;
let walls = makeMaze(mulberry32(7));
let S = newSearch('bfs');
let timer = null;
const cells = [];

function buildGrid() {
  const g = $('grid'); g.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const d = document.createElement('div');
    d.className = 'cell'; d.setAttribute('role', 'gridcell');
    d.addEventListener('click', () => {
      if (i === START || i === GOAL) return;
      walls[i] = !walls[i]; resetSearch();
    });
    g.appendChild(d); cells.push(d);
  }
}

function render() {
  const onFront = new Set(S.frontier.filter((v) => !S.done[v]));
  const path = new Set(S.found ? pathTo(S, GOAL) : []);
  let maxD = 1; for (let i = 0; i < N; i++) if (S.done[i] && S.dist[i] > maxD) maxD = S.dist[i];
  for (let i = 0; i < N; i++) {
    const d = cells[i]; let cls = 'cell'; let txt = ''; d.style.backgroundColor = ''; d.style.color = '';
    if (walls[i]) cls += ' wall';
    else {
      if (S.dist[i] >= 0 && (S.done[i] || onFront.has(i))) txt = String(S.dist[i]);
      if (S.done[i]) {
        const hue = 200 - Math.round(170 * S.dist[i] / maxD); // colour shifts from blue to orange as the wave moves outward
        d.style.backgroundColor = `hsl(${hue}, 65%, ${dark ? 34 : 80}%)`;
        if (dark) d.style.color = '#f2f5f8';
      }
      if (onFront.has(i)) cls += ' front';
      if (path.has(i)) cls += ' path';
      if (i === S.current && !S.finished) cls += ' cur';
    }
    if (i === START) { cls += ' start'; txt = 'S'; }
    if (i === GOAL) { cls += ' goal'; txt = S.found ? String(S.dist[GOAL]) : 'G'; }
    d.className = cls; d.textContent = txt;
  }
  $('nVisited').textContent = S.visited;
  $('nFront').textContent = onFront.size;
  $('nPath').textContent = S.found ? S.dist[GOAL] : '–';
  $('lblFront').textContent = S.mode === 'bfs' ? "In queue:" : "On stack:";
  $('qtitle').textContent = S.mode === 'bfs' ? "Queue, front → back: (x,y) distance" : "Stack, top → bottom: (x,y) depth";
  const items = S.frontier.filter((v) => !S.done[v]);
  const ordered = S.mode === 'bfs' ? items : items.slice().reverse();
  const q = $('qitems'); q.innerHTML = '';
  if (!ordered.length) { const e = document.createElement('span'); e.className = 'more'; e.textContent = "(empty)"; q.appendChild(e); }
  ordered.slice(0, 12).forEach((v) => {
    const e = document.createElement('span');
    e.textContent = `(${v % W},${Math.floor(v / W)}) ${S.dist[v]}`;
    q.appendChild(e);
  });
  if (ordered.length > 12) { const e = document.createElement('span'); e.className = 'more'; e.textContent = i18nFmt("+%n% more", { n: ordered.length - 12 }); q.appendChild(e); }
}

function setStatus(t, cls) { const s = $('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }

function finishMessage() {
  if (!S.found) { setStatus(i18nFmt("The goal is unreachable: the frontier ran empty after %visited% cells.", { visited: S.visited }), 'bad'); return; }
  if (S.mode === 'bfs') setStatus(i18nFmt("Goal reached! Shortest path: %len% steps, after exploring %visited% cells.", { len: S.dist[GOAL], visited: S.visited }), 'ok');
  else {
    const best = shortest(walls);
    setStatus(i18nFmt(S.dist[GOAL] === best ? "DFS reached the goal in %len% steps, which happens to be shortest (%best%) on this maze. Try another one." : "DFS reached the goal by a path of %len% steps, but the shortest one has only %best%.",
      { len: S.dist[GOAL], best, visited: S.visited }), S.dist[GOAL] === best ? 'ok' : 'bad');
  }
}

function doStep() {
  if (S.finished) { stop(); return; }
  step(S, walls); render();
  if (S.finished) { stop(); finishMessage(); }
  else setStatus(i18nFmt(S.mode === 'bfs' ? "Dequeued (%x%,%y%) at distance %d% and enqueued its unseen neighbours." : "Popped (%x%,%y%) at depth %d% and pushed its unvisited neighbours.",
    { x: S.current % W, y: Math.floor(S.current / W), d: S.dist[S.current] }), '');
}
function stop() { if (timer) { clearInterval(timer); timer = null; } $('run').textContent = "Run"; }
function run() {
  if (timer) { stop(); return; }
  if (S.finished) resetSearch();
  timer = setInterval(doStep, 55); $('run').textContent = "Pause";
}
function resetSearch() { stop(); S = newSearch($('mode').value); render(); setStatus("Edit the walls, then press Step or Run.", ''); }

$('step').addEventListener('click', () => { stop(); doStep(); });
$('run').addEventListener('click', run);
$('reset').addEventListener('click', resetSearch);
$('maze').addEventListener('click', () => { walls = makeMaze(Math.random); resetSearch(); });
$('clear').addEventListener('click', () => { walls = new Array(N).fill(false); resetSearch(); });
$('mode').addEventListener('change', resetSearch);
buildGrid(); render();

<p class="hint">Breadth-first search spreads from the start <b>S</b> like a wave, one layer at a time. Each explored cell shows its distance from S. Click cells to add or remove walls, then press <b>Step</b> or <b>Run</b>. Switch to DFS to see why a stack does not find the shortest path.</p>
<div class="bar">
  <label for="mode">Algorithm:</label>
  <select id="mode">
    <option value="bfs">BFS (queue)</option>
    <option value="dfs">DFS (stack)</option>
  </select>
</div>
<div id="grid" class="grid" role="grid" aria-label="Maze grid; click a cell to toggle a wall"></div>
<div class="stats">
  <span>Explored: <b id="nVisited">0</b></span>
  <span id="lblFront">In queue:</span> <b id="nFront">1</b>
  <span>Path length: <b id="nPath">–</b></span>
</div>
<div class="status" id="status">Edit the walls, then press Step or Run.</div>
<div class="queue">
  <div class="qtitle" id="qtitle">Queue, front → back: (x,y) distance</div>
  <div id="qitems" class="qitems"></div>
</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">Reset</button>
  <button id="maze" type="button" class="ghost">Random maze</button>
  <button id="clear" type="button" class="ghost">Clear walls</button>
</div>
<div class="legend">
  <span><i class="sw start"></i>Start</span>
  <span><i class="sw goal"></i>Goal</span>
  <span><i class="sw wall"></i>Wall</span>
  <span><i class="sw front"></i>Frontier</span>
  <span><i class="sw path"></i>Path found</span>
</div>

/* Colour palette as variables, with a dark-mode variant. */
:root { --fg: #1f2933; --muted: #52606d; --bg: #ffffff; --cell: #eef2f6; --wall: #2f3e4e;
        --accent: #1d3557; --front: #ffd166; --path: #e63946; --start: #2a9d8f; --goal: #7b2cbf; }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e4e9ef; --muted: #a7b4c2; --bg: #14181d; --cell: #232a33; --wall: #8a9aac;
          --accent: #74b3ce; --front: #c9a227; --path: #ff6b6b; --start: #3cc1b1; --goal: #b47ce8; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; }
.hint { font-size: .88rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.45; }
.bar { display: flex; align-items: center; gap: .5rem; margin-bottom: .45rem; font-size: .9rem; }
select { font: 600 13px system-ui, sans-serif; padding: .25rem .4rem; border-radius: 6px;
         border: 1px solid var(--accent); background: var(--bg); color: var(--fg); }
.grid { display: grid; grid-template-columns: repeat(15, 1fr); gap: 1px; width: 100%; max-width: 465px;
        background: var(--muted); border: 1px solid var(--muted); user-select: none; touch-action: manipulation; }
.cell { aspect-ratio: 1 / 1; background: var(--cell); display: flex; align-items: center; justify-content: center;
        font: 600 clamp(8px, 2.4vw, 11px) ui-monospace, monospace; color: #1f2933; cursor: pointer; overflow: hidden;
        transition: background-color .18s; }
.cell.wall { background: var(--wall); }
.cell.front { background: var(--front) !important; }
.cell.cur { outline: 2px solid var(--accent); outline-offset: -2px; }
.cell.path { background: var(--path) !important; color: #fff; }
.cell.start { background: var(--start) !important; color: #fff; }
.cell.goal { background: var(--goal) !important; color: #fff; }
.stats { display: flex; flex-wrap: wrap; gap: .3rem .9rem; font-size: .88rem; margin: .5rem 0 .2rem; }
.status { font-size: .92rem; font-weight: 600; min-height: 2.6em; margin: .25rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
@media (prefers-color-scheme: dark) { .status.ok { color: #5fd38d; } .status.bad { color: #ff8a8a; } }
.queue { font-size: .8rem; margin-bottom: .5rem; }
.qtitle { color: var(--muted); margin-bottom: .2rem; }
.qitems { display: flex; flex-wrap: wrap; gap: 3px; min-height: 1.4em; }
.qitems span { font: 12px ui-monospace, monospace; padding: 1px 5px; border-radius: 4px; background: var(--front); color: #1f2933; }
.qitems span.more { background: transparent; color: var(--muted); }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid var(--accent);
         background: var(--accent); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: var(--bg); color: var(--accent); }
.legend { display: flex; flex-wrap: wrap; gap: .3rem .8rem; font-size: .78rem; color: var(--muted); margin-top: .55rem; }
.sw { display: inline-block; width: 11px; height: 11px; border-radius: 2px; margin-right: 4px; vertical-align: -1px; }
.sw.start { background: var(--start); } .sw.goal { background: var(--goal); } .sw.wall { background: var(--wall); }
.sw.front { background: var(--front); } .sw.path { background: var(--path); }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const W = 15, H = 11, N = W * H;
const START = 0, GOAL = N - 1; // start at the top-left corner, goal at the bottom-right

// Small seeded random generator, so the first maze is always the same.
function mulberry32(a) { return function () { a |= 0; a = a + 0x6D2B79F5 | 0;
  let t = Math.imul(a ^ a >>> 15, 1 | a); t = t + Math.imul(t ^ t >>> 7, 61 | t) ^ t;
  return ((t ^ t >>> 14) >>> 0) / 4294967296; }; }

// Carve a perfect maze with a randomized depth-first walk on the even cells,
// then knock out extra walls so the maze has loops (and several possible routes).
function makeMaze(rnd) {
  const walls = new Array(N).fill(true);
  walls[START] = false;
  const stack = [START];
  while (stack.length) {
    const u = stack[stack.length - 1], r = Math.floor(u / W), c = u % W, opts = [];
    for (const [dr, dc] of [[-2, 0], [0, 2], [2, 0], [0, -2]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < H && nc >= 0 && nc < W && walls[nr * W + nc]) opts.push([nr, nc]);
    }
    if (!opts.length) { stack.pop(); continue; }
    const [nr, nc] = opts[Math.floor(rnd() * opts.length)];
    walls[((r + nr) / 2) * W + (c + nc) / 2] = false;
    walls[nr * W + nc] = false;
    stack.push(nr * W + nc);
  }
  // Open some walls between corridors to create cycles.
  for (let i = 0; i < N; i++) {
    const r = Math.floor(i / W), c = i % W;
    if (walls[i] && (r % 2) + (c % 2) === 1 && rnd() < 0.25) walls[i] = false;
  }
  return walls;
}

// Open neighbours of cell i in the order up, right, down, left.
function neighbors(i, walls) {
  const r = Math.floor(i / W), c = i % W, out = [];
  if (r > 0) out.push(i - W);
  if (c < W - 1) out.push(i + 1);
  if (r < H - 1) out.push(i + W);
  if (c > 0) out.push(i - 1);
  return out.filter((j) => !walls[j]);
}

// Search state: dist = layer number (-1 = unseen), parent pointers, explored flags, frontier.
function newSearch(mode) {
  const s = { mode, dist: new Array(N).fill(-1), parent: new Array(N).fill(-1), done: new Array(N).fill(false),
              frontier: [START], finished: false, found: false, visited: 0, current: -1 };
  s.dist[START] = 0;
  return s;
}

// One step: take a cell from the frontier (front of the queue for BFS, top of the stack for DFS),
// mark it explored and add its unseen neighbours with distance + 1.
function step(s, walls) {
  if (s.finished) return;
  if (s.mode === 'dfs') while (s.frontier.length && s.done[s.frontier[s.frontier.length - 1]]) s.frontier.pop();
  if (!s.frontier.length) { s.finished = true; return; }
  const u = s.mode === 'bfs' ? s.frontier.shift() : s.frontier.pop();
  s.done[u] = true; s.visited++; s.current = u;
  if (u === GOAL) { s.finished = true; s.found = true; return; }
  const nb = neighbors(u, walls);
  if (s.mode === 'dfs') nb.reverse(); // so the stack pops neighbours in the same up/right/down/left order
  for (const v of nb) {
    if (s.mode === 'bfs' ? s.dist[v] < 0 : !s.done[v]) {
      s.dist[v] = s.dist[u] + 1; s.parent[v] = u; s.frontier.push(v);
    }
  }
}

// Follow parent pointers back from the goal to rebuild the path.
function pathTo(s, t) { const p = []; if (s.dist[t] < 0) return p; for (let v = t; v !== -1; v = s.parent[v]) p.push(v); return p.reverse(); }

// Plain BFS to the end, used to compare the DFS path with the true shortest path.
function shortest(walls) {
  const s = newSearch('bfs');
  while (!s.finished) step(s, walls);
  return s.found ? s.dist[GOAL] : -1;
}

// Drawing and buttons.
const $ = (id) => document.getElementById(id);
const dark = window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches;
let walls = makeMaze(mulberry32(7));
let S = newSearch('bfs');
let timer = null;
const cells = [];

function buildGrid() {
  const g = $('grid'); g.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const d = document.createElement('div');
    d.className = 'cell'; d.setAttribute('role', 'gridcell');
    d.addEventListener('click', () => {
      if (i === START || i === GOAL) return;
      walls[i] = !walls[i]; resetSearch();
    });
    g.appendChild(d); cells.push(d);
  }
}

function render() {
  const onFront = new Set(S.frontier.filter((v) => !S.done[v]));
  const path = new Set(S.found ? pathTo(S, GOAL) : []);
  let maxD = 1; for (let i = 0; i < N; i++) if (S.done[i] && S.dist[i] > maxD) maxD = S.dist[i];
  for (let i = 0; i < N; i++) {
    const d = cells[i]; let cls = 'cell'; let txt = ''; d.style.backgroundColor = ''; d.style.color = '';
    if (walls[i]) cls += ' wall';
    else {
      if (S.dist[i] >= 0 && (S.done[i] || onFront.has(i))) txt = String(S.dist[i]);
      if (S.done[i]) {
        const hue = 200 - Math.round(170 * S.dist[i] / maxD); // colour shifts from blue to orange as the wave moves outward
        d.style.backgroundColor = `hsl(${hue}, 65%, ${dark ? 34 : 80}%)`;
        if (dark) d.style.color = '#f2f5f8';
      }
      if (onFront.has(i)) cls += ' front';
      if (path.has(i)) cls += ' path';
      if (i === S.current && !S.finished) cls += ' cur';
    }
    if (i === START) { cls += ' start'; txt = 'S'; }
    if (i === GOAL) { cls += ' goal'; txt = S.found ? String(S.dist[GOAL]) : 'G'; }
    d.className = cls; d.textContent = txt;
  }
  $('nVisited').textContent = S.visited;
  $('nFront').textContent = onFront.size;
  $('nPath').textContent = S.found ? S.dist[GOAL] : '–';
  $('lblFront').textContent = S.mode === 'bfs' ? "In queue:" : "On stack:";
  $('qtitle').textContent = S.mode === 'bfs' ? "Queue, front → back: (x,y) distance" : "Stack, top → bottom: (x,y) depth";
  const items = S.frontier.filter((v) => !S.done[v]);
  const ordered = S.mode === 'bfs' ? items : items.slice().reverse();
  const q = $('qitems'); q.innerHTML = '';
  if (!ordered.length) { const e = document.createElement('span'); e.className = 'more'; e.textContent = "(empty)"; q.appendChild(e); }
  ordered.slice(0, 12).forEach((v) => {
    const e = document.createElement('span');
    e.textContent = `(${v % W},${Math.floor(v / W)}) ${S.dist[v]}`;
    q.appendChild(e);
  });
  if (ordered.length > 12) { const e = document.createElement('span'); e.className = 'more'; e.textContent = i18nFmt("+%n% more", { n: ordered.length - 12 }); q.appendChild(e); }
}

function setStatus(t, cls) { const s = $('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }

function finishMessage() {
  if (!S.found) { setStatus(i18nFmt("The goal is unreachable: the frontier ran empty after %visited% cells.", { visited: S.visited }), 'bad'); return; }
  if (S.mode === 'bfs') setStatus(i18nFmt("Goal reached! Shortest path: %len% steps, after exploring %visited% cells.", { len: S.dist[GOAL], visited: S.visited }), 'ok');
  else {
    const best = shortest(walls);
    setStatus(i18nFmt(S.dist[GOAL] === best ? "DFS reached the goal in %len% steps, which happens to be shortest (%best%) on this maze. Try another one." : "DFS reached the goal by a path of %len% steps, but the shortest one has only %best%.",
      { len: S.dist[GOAL], best, visited: S.visited }), S.dist[GOAL] === best ? 'ok' : 'bad');
  }
}

function doStep() {
  if (S.finished) { stop(); return; }
  step(S, walls); render();
  if (S.finished) { stop(); finishMessage(); }
  else setStatus(i18nFmt(S.mode === 'bfs' ? "Dequeued (%x%,%y%) at distance %d% and enqueued its unseen neighbours." : "Popped (%x%,%y%) at depth %d% and pushed its unvisited neighbours.",
    { x: S.current % W, y: Math.floor(S.current / W), d: S.dist[S.current] }), '');
}
function stop() { if (timer) { clearInterval(timer); timer = null; } $('run').textContent = "Run"; }
function run() {
  if (timer) { stop(); return; }
  if (S.finished) resetSearch();
  timer = setInterval(doStep, 55); $('run').textContent = "Pause";
}
function resetSearch() { stop(); S = newSearch($('mode').value); render(); setStatus("Edit the walls, then press Step or Run.", ''); }

$('step').addEventListener('click', () => { stop(); doStep(); });
$('run').addEventListener('click', run);
$('reset').addEventListener('click', resetSearch);
$('maze').addEventListener('click', () => { walls = makeMaze(Math.random); resetSearch(); });
$('clear').addEventListener('click', () => { walls = new Array(N).fill(false); resetSearch(); });
$('mode').addEventListener('change', resetSearch);
buildGrid(); render();

Result

Console

Watch the numbers: they grow in perfect rings around S, and the frontier never holds more than two consecutive distances at once. When the goal is dequeued, the red path is guaranteed to be as short as possible. Now switch the algorithm to DFS and run it again on the same maze: the stack sends the search down long corridors, and the path it reports is usually longer than the BFS path. Generate a few random mazes to see how big the difference can get.

The Real Complexity

BFS is about as cheap as a graph algorithm can be: it looks at every vertex and every edge a constant number of times.

Time: with adjacency lists, $O(V + E)$ . Each vertex is enqueued and dequeued at most once ( $O(V)$ ), and each adjacency list is scanned once, when its vertex is dequeued — $\sum_{u} \deg(u) = 2E$ for an undirected graph, $E$ for a directed one. With an adjacency matrix, scanning a row costs $V$ , so the total becomes $O(V^{2})$ .
Space: $O(V)$ for dist, parent and the queue. On a grid of $W \times H$ cells, $V = WH$ and $E \le 2WH$ , so solving a maze is linear in its area.
Best and worst case: if you stop when the target is dequeued, the best case is $O(1)$ (the target is the source) and the worst case is the full $O(V + E)$ . The work done is the number of vertices closer to $s$ than the target, plus their edges.

Why the layer number is the shortest distance. Write $\delta(v)$ for the true shortest-path distance. Two facts drive the proof:

At every moment the queue holds vertices whose dist values are non-decreasing from front to back and differ by at most 1: $d, d, \dots, d, d+1, \dots, d+1$ . Dequeuing a vertex with value $d$ only appends vertices with value $d+1$ , so this shape is preserved. Hence vertices leave the queue in non-decreasing order of dist — the layers are monotone.
By induction on $\delta(v)$ : let $u$ be the predecessor of $v$ on some shortest path, so $\delta(u) = \delta(v) - 1$ . By the induction hypothesis $u$ gets dist[u] $= \delta(u)$ , and because of monotonicity no vertex with a larger dist is dequeued before $u$ . So $v$ is discovered no later than when $u$ is processed, and receives dist[v] $= \delta(v)$ — never less, since every discovered vertex really is reachable by a path of length dist.

BFS is Dijkstra with all weights equal to 1. In Dijkstra's algorithm a priority queue always extracts the closest unsettled vertex. When every edge costs 1, the tentative distances in the frontier take only two consecutive values, so a plain FIFO queue already delivers them in sorted order and the $\log V$ factor of the heap disappears. As soon as edges have different weights, BFS is no longer correct and you need Dijkstra (or Bellman–Ford for negative weights).

Variants worth knowing

Bipartiteness test: colour each vertex by the parity of its layer. The graph is bipartite (2-colourable) if and only if no edge joins two vertices of the same layer; an edge inside a layer closes an odd cycle. Total cost: still $O(V + E)$ .
Multi-source BFS: put several sources in the queue at distance 0. Each vertex then gets its distance to the nearest source — handy for "distance to the closest hospital" maps or for fire spreading on a grid.
0-1 BFS: if edge weights are only 0 or 1, use a double-ended queue: push the neighbour to the front for a 0-edge and to the back for a 1-edge. It computes exact shortest paths in $O(V + E)$ , without a heap.
Bidirectional BFS: search from the source and the target at the same time and stop when the frontiers meet. With branching factor $b$ and distance $d$ , this explores roughly $2b^{d/2}$ vertices instead of $b^{d}$ — a huge saving on large implicit graphs.

Where It Matters

Whenever "fewest steps" is the question and every step costs the same, BFS is the answer — and it shows up in surprising places:

Mazes, grids and games: robots, video-game units and the original Lee router all need the fewest moves across a grid. BFS is the baseline that heuristic searches like A* improve on; the mazes themselves often come from maze-generation algorithms built on random traversals.
Degrees of separation: in a social network, your friends are layer 1, their friends layer 2, and so on. BFS from one person measures how few hops connect them to everyone else — the measurement behind the "six degrees" phenomenon of small-world networks.
Web crawlers: starting from seed pages and following links layer by layer reaches the most-linked, closest pages first, and the queue doubles as the crawl frontier.
Flood fill: the paint-bucket tool in an image editor floods all connected pixels of the same colour; a queue-based fill is a BFS over pixels, and so is labelling the connected regions of an image.
Garbage collection: Cheney's copying collector (1970) copies live objects into a new memory region and uses that region itself as the BFS queue, with two pointers marking the front and the back. Read more in garbage collection.
Network broadcast: flooding a message through a peer-to-peer or sensor network reaches nodes in BFS order, and the BFS tree tells you the fewest hops to each one.
Puzzles with the fewest moves: every position of the 15-puzzle or a Rubik's cube is a vertex and every legal move an edge. BFS finds optimal solutions on small state graphs, and pattern databases for large puzzles are built by a breadth-first sweep backwards from the solved state.
Flows and matchings: the Edmonds–Karp variant of maximum flow picks each augmenting path with BFS (always a shortest one), which guarantees a polynomial number of rounds.

Conclusion

Breadth-first search is the cleanest example of a data structure doing the thinking. A first-in, first-out queue forces the exploration to happen in order of distance, and that single property gives you, for free, the shortest path to every reachable vertex in $O(V + E)$ time.

It is also a starting point. Replace the queue with a priority queue and you get Dijkstra's algorithm; replace it with a stack and you get depth-first search; run it from both ends, from many sources or over a deque and you get the variants that power routing, games and network tools. Moore wanted a way out of a maze, Lee wanted to route wires — and the idea they found is still one of the first algorithms every programmer should know by heart.

Comments

Loading comments...

https://www.kipuhub.com/en/article/breadth-first-search/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Breadth-First Search (BFS)

A queue, a wave, and the shortest path in every unweighted graph