Breadth-First Search (BFS): Level-by-Level Graph Traversal

Breadth-First Search (BFS) explores a graph in layers: first vertices one edge from the source, then two edges away, then three, and so on.

Its main data structure is a FIFO queue. This level ordering is what makes BFS the standard solution for shortest paths in unweighted or equal-cost graphs.

Basic implementation

function bfs(graph, start) {
  const queue = [start];
  let head = 0;

  const visited = new Set([start]);
  const order = [];

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

Mark vertices visited when they are enqueued, not when they are removed, to prevent duplicate queue entries.

Shortest paths

The first time BFS discovers a vertex is the minimum number of edges from the source.

function bfsDistances(graph, start) {
  const queue = [start];
  let head = 0;
  const distance = { [start]: 0 };

  while (head < queue.length) {
    const current = queue[head++];

    for (const next of graph[current] ?? []) {
      if (distance[next] !== undefined) continue;

      distance[next] = distance[current] + 1;
      queue.push(next);
    }
  }

  return distance;
}

Store parent[next] = current if the actual shortest path must be reconstructed.

Why not arbitrary weighted graphs?

BFS minimizes edge count, not total weight. With unequal positive costs, Dijkstra is usually appropriate.

BFS vs DFS

| Feature | BFS | DFS | |---|---|---| | Structure | Queue | Stack / recursion | | Pattern | Level by level | Depth first | | Unweighted shortest path | Yes | No guarantee | | Typical use | nearest state, levels, shortest moves | recursion, cycles, backtracking |

Trees

On trees, BFS is commonly called level-order traversal.

Grids and mazes

Treat each cell as a vertex and each legal equal-cost move as an edge. BFS then finds the minimum number of moves from start to target.

Social networks

Users are vertices and relationships are edges. BFS can compute degrees of separation and nearest reachable users.

Web crawling

Pages are vertices and hyperlinks are edges. BFS naturally crawls depth 0, then depth 1, then depth 2.

Connected components

Run BFS from each still-unvisited vertex to discover all components in an undirected graph.

Multi-Source BFS

Insert every source into the queue initially with distance zero. This is useful for nearest-facility, fire-spread, infection-spread, and nearest-exit problems.

function multiSourceBFS(graph, sources) {
  const queue = [...sources];
  let head = 0;
  const distance = new Map();

  for (const source of sources) {
    distance.set(source, 0);
  }

  while (head < queue.length) {
    const current = queue[head++];

    for (const next of graph[current] ?? []) {
      if (distance.has(next)) continue;

      distance.set(next, distance.get(current) + 1);
      queue.push(next);
    }
  }

  return distance;
}

Bidirectional BFS

When start and target are both known, searching from both ends can reduce the explored state space dramatically.

0-1 BFS

If weights are only 0 or 1, use a deque:

• weight 0 → front
• weight 1 → back

This specialized algorithm is called 0-1 BFS.

Bipartite checking

BFS can color alternating levels with two colors. An edge joining equal colors proves the graph is not bipartite.

State-space search

Many non-obvious problems are graphs in disguise:

State = Vertex
Operation = Edge

Examples include Word Ladder, knight moves, puzzle transformations, and minimum button presses.

Complexity

With adjacency lists:

Time: O(V + E)
Space: O(V)

With an adjacency matrix, neighbor scanning may require O(V²) time.

Common mistakes

• forgetting visited,
• marking visited too late,
• using BFS for general weighted shortest paths,
• using repeated shift() on large JavaScript queues,
• forgetting disconnected components,
• not storing parents when the actual path is required,
• incorrect grid boundaries.

TypeScript

type Graph = Record<string, string[]>;

function bfs(
  graph: Graph,
  start: string
): string[] {
  const queue: string[] = [start];
  let head = 0;

  const visited = new Set<string>([start]);
  const order: string[] = [];

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;

      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

When to use BFS

Use BFS for unweighted shortest paths, minimum moves, nearest states, tree levels, equal-cost grids, multi-source distance, and bipartite checks.

Summary

BFS is a queue-based, level-order traversal. Its defining practical advantage is that in unweighted or equal-cost graphs, first discovery gives minimum edge distance.

The recognition pattern is:

nearest state?
minimum moves?
unweighted shortest path?
level-order traversal?

→ BFS