Breadth-First Search

Hook problem

Suppose every edge has the same cost: one step. From A, which nodes are 0, 1, 2, and 3 steps away?

First naive idea

You could walk deeply down one path, such as A -> B -> D -> G, before checking nearby alternatives. That can reach a far node while closer options are still waiting.

Where it breaks

If discovery order is allowed to go deep, it no longer guarantees nondecreasing distance from the start. The small directed comparison isolates the policy difference: a FIFO queue preserves layers, while a stack-like policy can expose deeper nodes first.

The core invention

BFS keeps a queue: discovered nodes wait in first-in, first-out order. When B discovers D and E, C still stays in front of them because C was discovered earlier.

Interactive visual demo

Formal version

BFS starts from a source s, discovers undiscovered neighbors, records distance[neighbor] = distance[current] + 1, records parent[neighbor] = current, and enqueues the neighbor.

This page uses discovered or visited for nodes that have already been found and queued. expanded means a node has been dequeued and fully scanned.

Implementation sketch

function bfs(start: string, graph: Record<string, string[]>) {
  const queue = [start];
  let head = 0;
  const visited = new Set([start]);
  const distance: Record<string, number> = { [start]: 0 };
  const parent: Record<string, string | undefined> = { [start]: undefined };

  while (head < queue.length) {
    const current = queue[head++];
    for (const neighbor of graph[current]) {
      if (visited.has(neighbor)) continue;
      visited.add(neighbor);
      distance[neighbor] = distance[current] + 1;
      parent[neighbor] = current;
      queue.push(neighbor);
    }
  }

  return { distance, parent };
}

The visual “dequeue” maps to queue[head++], not queue.shift(), so the TypeScript sketch keeps linear-time queue behavior.

Correctness intuition

The queue can contain a boundary like [remaining layer k | newly discovered layer k+1]. The key is that all remaining layer-k nodes stay before layer-k+1 nodes, so a farther node cannot expand early.

Complexity

With an adjacency list, BFS discovers each node once and scans each adjacency row when that node expands. The total time is O(V + E), and the queue, distance table, parent table, and visited set use O(V) space.

Common confusions

Marking a node when it is discovered prevents duplicate queue entries. In the trace, E and F both try G, but G keeps the parent from its first discovery.

BFS finds shortest paths by edge count only. If edges have different costs, the fewest-edge path may not be the cheapest path.

Distance is a number. Parent pointers recover an actual path tree.

Connections in the graph

BFS depends on graph basics: it repeatedly asks for the current node’s immediate neighbors. Dijkstra keeps the frontier-and-distance idea, but chooses the next node by smallest total cost instead of queue order.

Exercises

1. After expanding B, why does C stay before D and E?
2. When E scans G, why does parent[G] stay D?
3. What changes if the queue is replaced by a stack?
4. Why does the weighted triangle require Dijkstra instead of BFS?

Graph connections : Breadth-First Search