A queue makes a strong promise: whatever goes in first comes out first. Point that promise at a graph and you get breadth-first search — visit a node, enqueue its unvisited neighbors, repeat. Because the queue only ever hands back what it received earliest, every node one step away from the start gets processed before any node two steps away, which is exactly what "process the graph one distance-from-start layer at a time" means. That layer-by-layer order is also what guarantees BFS finds the shortest path in an unweighted graph — the first time it reaches a node is provably via the fewest possible steps.
Click any cell to toggle a wall (green is the start, orange is the end — fixed). Step through the search and watch the queue below the grid: the current cell being dequeued gets a bold border, cells it discovers get added to the queue's tail and shaded, and once the end is dequeued the shortest path lights up. Edit the walls, then press Reset to re-run the search against your new maze.
The queue is the whole mechanism. Every cell is enqueued exactly once, the moment it's first
discovered, and marked visited right then — not when it's later dequeued — so the same cell can
never be queued twice even if several already-processed cells border it. Because the queue is
FIFO, all of layer k (cells exactly k steps from the start) finish
enqueuing before any cell from layer k+1 is dequeued. That ordering is what makes the
first visit to any cell the shortest visit — swap the queue for a stack and you get depth-first
search instead, which still visits every reachable cell but gives up the shortest-path
guarantee, since a stack can dive down one long branch before ever coming back for a closer
one.
Grid version, tracking a parent pointer per cell so the path can be reconstructed once the end is found:
function bfs(grid, rows, cols, start, end) {
const key = (r, c) => r * cols + c;
const visited = new Array(rows * cols).fill(false);
const parent = new Array(rows * cols).fill(-1);
const queue = [key(...start)];
visited[key(...start)] = true;
let head = 0;
const endKey = key(...end);
while (head < queue.length) {
const cur = queue[head++];
if (cur === endKey) break;
const r = Math.floor(cur / cols), c = cur % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nk = nr * cols + nc;
if (visited[nk] || grid[nk] === WALL) continue;
visited[nk] = true;
parent[nk] = cur;
queue.push(nk);
}
}
if (!visited[endKey]) return null; // unreachable
const path = [];
for (let cur = endKey; cur !== -1; cur = parent[cur]) path.push(cur);
return path.reverse();
}Note the head pointer (head++) instead of queue.shift() — the same
O(1)-per-dequeue trick from the queue entry.
Shifting a plain array on every dequeue would make this O(n) per step instead of
O(1), turning an O(V + E) algorithm quadratic on dense grids.
Marking visited too late. If you mark a node visited when it's dequeued rather than when it's enqueued, the same node can be pushed onto the queue multiple times by different neighbors before it's ever processed — still eventually correct, but wasteful, and in graphs with many shared neighbors it can blow up the queue size badly. Mark on enqueue, not dequeue.
It only finds shortest paths in unweighted graphs. BFS's guarantee rests on
every edge costing the same "one step." Add weighted edges (a road network where blocks have
different lengths) and BFS's first-visit-is-shortest logic breaks — that's what
Dijkstra's algorithm generalizes it into, replacing the
plain queue with a heap-backed priority queue ordered by
accumulated cost instead of by discovery order. There's a narrower middle case worth its own
entry: if every edge costs exactly 0 or 1, 0-1 BFS keeps
BFS's plain O(V + E) bound by swapping the queue for a
deque instead of paying for a full priority queue.
Forgetting the visited check reintroduces infinite loops. Without it, BFS on a graph with a cycle (or a grid, where you can walk back the way you came) will re-enqueue cells forever. The visited set is what turns "explore a graph" into "explore a graph exactly once."
One circle of "distance from start" costs more than two smaller ones. BFS finds
the shortest path by growing a single circle outward from the start until it happens to reach the
end — for a graph with branching factor b and a d-step answer, that's
roughly bd cells touched. Bidirectional search keeps the exact same
shortest-path guarantee while growing two such circles at once, one from each end, and stopping the
moment they meet — roughly 2·bd/2 cells instead, a difference that gets
dramatic fast once branching factor grows past a grid's capped-at-4 neighbors.
Time: O(V + E) — every vertex is enqueued once and every edge is
inspected once (twice, from each endpoint, on an undirected graph like this grid). On an
r × c grid, V = r·c and each cell has at most 4 edges, so this is
O(r·c). Space: O(V) for the visited array, the parent
array, and the queue itself, which in the worst case holds an entire layer of the graph at once.
This same "shortest path by edge count" guarantee is the one piece maximum flow borrows directly: repeatedly running a plain BFS like this one, but on a graph's residual capacities instead of its walls, is exactly what keeps that algorithm's iteration count bounded.
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.