jsschools

Breadth-First Search (BFS)

Explores a graph level by level using a queue, visiting all neighbours of a node before moving to the next level; finds shortest paths in unweighted graphs.

Spec ↗

Syntax

bfs(graph, start)

Parameters

NameTypeRequiredDescription
graph Map<number, number[]> Yes Adjacency list representation. Keys are node ids, values are arrays of neighbour node ids.
start number Yes The source node from which traversal begins.

Returns

Map<number, number> — A map from each reachable node to its shortest distance from start.

Examples

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const neighbour of graph.get(node) ?? []) {
      if (!dist.has(neighbour)) {
        dist.set(neighbour, dist.get(node) + 1);
        queue.push(neighbour);
      }
    }
  }
  return dist;
}

const graph = new Map([
  [0, [1, 2]],
  [1, [0, 3, 4]],
  [2, [0]],
  [3, [1]],
  [4, [1]],
]);
console.log([...bfs(graph, 0)]);
Output 
[ [ 0, 0 ], [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 2 ] ]

// BFS to check bipartiteness (2-colouring)
function isBipartite(graph) {
  const color = new Map();
  for (const start of graph.keys()) {
    if (color.has(start)) continue;
    color.set(start, 0);
    const q = [start];
    while (q.length) {
      const u = q.shift();
      for (const v of graph.get(u) ?? []) {
        if (!color.has(v)) { color.set(v, 1 - color.get(u)); q.push(v); }
        else if (color.get(v) === color.get(u)) return false;
      }
    }
  }
  return true;
}

const bipartite = new Map([[0,[1,3]],[1,[0,2]],[2,[1,3]],[3,[0,2]]]);
const triangle  = new Map([[0,[1,2]],[1,[0,2]],[2,[0,1]]]);
console.log(isBipartite(bipartite));
console.log(isBipartite(triangle));
Output 
true
false

Notes

| Case | Time | Space | |---------|------------|--------| | Best | O(V + E) | O(V) | | Average | O(V + E) | O(V) | | Worst | O(V + E) | O(V) | V = vertices, E = edges. BFS guarantees the **shortest path** (in terms of edge count) in an unweighted graph. Use a `Set` or `Map` for visited tracking to avoid revisiting nodes. `queue.shift()` is O(n) — for large graphs replace with a proper O(1) deque. BFS is the basis for 0-1 BFS (deque with weights 0/1), multi-source BFS, and bidirectional BFS.

See also