Breadth-First Search

Implement BFS using a queue and a visited set to traverse any graph layer by layer, and use it to find shortest paths in unweighted graphs in O(V+E) time.

5 min read Level 2/5 #dsa#graph#bfs

What you'll learn

Implement BFS iteratively with a queue and visited set
Explain why BFS guarantees shortest hop count in unweighted graphs
Analyse BFS time and space complexity as O(V+E)

Breadth-First Search (BFS) visits every vertex reachable from a source in order of increasing distance. Because it explores all vertices at distance d before any at distance d+1, BFS is the natural algorithm for shortest paths in graphs with no edge weights.

The Queue + Visited Pattern

BFS uses a FIFO queue to schedule vertices and a Set to avoid revisiting them. Without the visited guard the algorithm loops forever on cycles.

// graph: Map<number, Set<number>>  (unweighted, undirected)
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);

    for (const neighbour of graph.get(node) ?? []) {
      if (!visited.has(neighbour)) {
        visited.add(neighbour);
        queue.push(neighbour);
      }
    }
  }
  return order;
}

Shortest Path with BFS

To find the shortest path between two vertices, track each node’s predecessor while BFS runs, then reconstruct the path by walking backwards.

function shortestPath(graph, start, end) {
  const prev = new Map([[start, null]]);
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    if (node === end) break;

    for (const neighbour of graph.get(node) ?? []) {
      if (!prev.has(neighbour)) {
        prev.set(neighbour, node);
        queue.push(neighbour);
      }
    }
  }

  if (!prev.has(end)) return null; // no path

  const path = [];
  for (let cur = end; cur !== null; cur = prev.get(cur)) {
    path.push(cur);
  }
  return path.reverse();
}

// Example: 0-1, 0-2, 1-3, 2-3
import { buildAdjList } from "./graph-representations";
const g = buildAdjList(4, [[0,1],[0,2],[1,3],[2,3]]);
console.log(shortestPath(g, 0, 3)); // [0, 1, 3] or [0, 2, 3]

Complexity

Metric	Value	Reason
Time	O(V+E)	Each vertex and edge visited once
Space	O(V)	Queue and visited set hold vertices

When to Use BFS

Use BFS when you need the minimum number of hops, level-order traversal, or reachability in an unweighted graph. For weighted shortest paths, reach for Dijkstra’s algorithm instead.

Up Next

Learn Depth-First Search — the recursive cousin of BFS — and how it powers cycle detection with three-color marking.

Depth-First Search →