BFS Traversal Template
Breadth-first search visits every reachable node in non-decreasing distance from the start, which makes it the right algorithm for shortest-path-in-unweighted-graph, level-order tree traversal, and grid-flood problems. This snippet covers the canonical queue + visited skeleton, the level-by-level form for tree-style problems, and the multi-source variant for problems like 'rotting oranges' where many start points share a frontier.
1,125 views
29
function bfs(start, getNeighbors) {
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const next of getNeighbors(node)) {
if (visited.has(next)) continue;
visited.add(next);
queue.push(next);
}
}
return order;
}
const graph = { A: ['B', 'C'], B: ['D'], C: ['D', 'E'], D: [], E: [] };
console.log(bfs('A', (n) => graph[n])); // [A, B, C, D, E]The canonical BFS keeps a Set of visited nodes and a queue of frontier nodes. Marking a node visited at the moment it enters the queue (not when it dequeues) is the easy mistake to avoid: forgetting to mark on enqueue can re-enqueue the same node many times and blow up runtime. Array.shift() is O(n) for large arrays; for big graphs use a real queue or an index-pointer trick (see next accordion). On small graphs the simplicity wins.
function bfsLevels(start, getNeighbors) {
const visited = new Set([start]);
let frontier = [start];
const levels = [];
while (frontier.length > 0) {
levels.push(frontier);
const next = [];
for (const node of frontier) {
for (const n of getNeighbors(node)) {
if (visited.has(n)) continue;
visited.add(n);
next.push(n);
}
}
frontier = next;
}
return levels;
}
const tree = { 1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: [] };
console.log(bfsLevels(1, (n) => tree[n])); // [[1], [2, 3], [4, 5, 6]]Some problems care which 'level' (distance from start) each node belongs to: level-order tree traversal, computing the shortest distance to every reachable node, finding all leaves at the same depth. Building the next frontier from the current one in a single pass groups nodes by level naturally, without storing per-node depths. The trade-off is two arrays per level instead of a queue, but the level-grouped output is exactly the shape the caller usually wants.
function multiSourceBfs(sources, getNeighbors) {
const visited = new Set(sources);
let frontier = [...sources];
let distance = 0;
const dist = new Map();
for (const s of sources) dist.set(s, 0);
while (frontier.length > 0) {
distance++;
const next = [];
for (const node of frontier) {
for (const n of getNeighbors(node)) {
if (visited.has(n)) continue;
visited.add(n);
dist.set(n, distance);
next.push(n);
}
}
frontier = next;
}
return dist;
}
const rooms = { A: ['B'], B: ['C', 'D'], C: ['E'], D: [], E: [] };
console.log([...multiSourceBfs(['A', 'D'], (n) => rooms[n]).entries()]);Multi-source BFS seeds the queue with every starting node at once, then runs a normal BFS. Because all sources are at distance 0, the level-by-level frontier still respects shortest-path semantics. This is the trick that solves 'rotting oranges' (every rotten orange spreads at the same rate), 'walls and gates' (every gate is distance 0), and most grid-distance problems. The pattern generalises beyond grids to any graph where multiple anchor nodes are equally close to themselves.