Breadth-First Search — Graph Algorithms

Overview

What this concept solves

Breadth-First Search visits a graph in expanding rings. Start at one node. Visit all of its neighbours. Then all of their unvisited neighbours. Then theirs. After k rounds, you've seen every node that's exactly k edges away from the start — and crucially, you've seen them in that order.

The whole algorithm is a single data structure: a queue. You enqueue the start, then loop — dequeue a node, mark it visited, enqueue every unvisited neighbour. That's it. Eight lines of code, O(V + E) time, O(V) space. The queue is what enforces the ring-by-ring order: nodes enqueued earlier (closer to the start) get dequeued before nodes enqueued later (further out).

BFS is the right tool whenever you need to count edges or find a shortest path in an unweighted graph. The first time a node leaves the queue, the path it took to get there is already the shortest one — because every shorter path would have reached it first. That property is so useful that BFS shows up under a dozen other names: level-order traversal in trees, breadth-first crawl in web spiders, k-hop neighbour queries in social networks.

Mechanics

How it works

The algorithm in five lines

Put the start node in a queue. Mark its distance as 0.
Loop while the queue isn't empty: take the front node off.
For each of its neighbours: if you haven't seen this neighbour yet, mark its distance as the current node's distance + 1 and enqueue it.
Repeat until the queue empties.
Every reachable node now has its shortest distance from the start.

Why the queue gives shortest paths

Nodes are added to the queue in increasing distance order: distance-0 first (the start), then distance-1, then distance-2.
When you dequeue a distance-k node, its unvisited neighbours are at distance k+1 — they get marked once, with that distance, and never touched again.
First-seen = shortest, because a longer path would have been blocked by a shorter one that ran first.
This only works if every edge counts the same. Weighted edges break the invariant — that's why you need Dijkstra once weights enter the picture.

Three sets, not two

It's tempting to track only 'visited / unvisited.' But BFS really has three states: unseen (we haven't touched it), queued (it's in the queue, distance assigned, neighbours not yet expanded), and visited (it's been dequeued, neighbours expanded). Forgetting to mark a node as queued the moment you enqueue it — not when you dequeue it — is the classic bug: you'll enqueue the same node many times and the runtime balloons.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Breadth-First Search

About this simulation

A seven-node graph, a queue, and a visit order. Press Play to watch BFS sweep outward in expanding rings, or use Step / Back to walk one dequeue at a time. The Start dropdown lets you re-run from any node so you can compare distance fields.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through one full BFS

Press Play and watch the orange ring sweep outward from A. Notice how every distance-1 neighbour (B, C) gets enqueued before any distance-2 neighbour. The colour transitions go unseen → queued → visited — same three-state pattern from the explanation.

try 02

Step through one dequeue at a time

Hit Step to advance and Back to rewind. Every step dequeues one node, marks it visited, and enqueues its unseen neighbours. Watch the In queue and Visited counters: the queue grows on the early steps (lots of new neighbours), then shrinks as the frontier hits already-seen nodes.

try 03

Try a different start node

Pick a leaf like D or G in the Start dropdown. The visit order changes completely — and so do the distances. From a leaf, BFS has to crawl back up through its only neighbour before fanning out, so the distance field looks lopsided.

try 04

Find the longest shortest path

Set start to A and look at the highest distance label in the graph. That number is the graph's eccentricity from A — the farthest any node is from your start. Try other start nodes; the maximum across all starts is the graph's diameter, which BFS computes in V² total time.

In practice

When to use it — and what you give up

When it's the right tool

Shortest path in an unweighted graph — fewest hops between two web pages, friends-of-friends in a social network, fewest moves in a sliding puzzle.
Level-by-level processing — render a tree level by level; rank pages by distance from the seed in a crawl.
Connectivity — 'is there any path from A to B?' BFS answers it in O(V + E) and proves the shortest one in the same pass.
Bipartite check — colour the start node 0, every neighbour 1, every grand-neighbour 0; an edge connecting two same-colour nodes proves the graph isn't bipartite.
Web crawling — BFS gives you a 'concentric circle' crawl, so you cover the whole site before going deep into one corner.

When to reach for something else

Weighted edges — use Dijkstra. BFS treats every edge as cost 1, so it'll return wrong answers on a graph where some edges are 'expensive.'
You want a topological order or to find cycles — use DFS. Its post-order is the topo sort; its grey-edge detector finds cycles.
The graph is huge and the goal is somewhere specific — use A. BFS expands everywhere; A expands toward the goal.

Pros

Linear time — O(V + E). Touches every node and every edge exactly once.
Shortest path is free — first-seen distance is the answer; no extra bookkeeping.
Iterative — uses a queue, not recursion. Works fine on graphs with millions of nodes where DFS would blow the stack.
Easy to parallelise — each frontier ring can be expanded independently, which is why BFS underpins distributed graph engines like Pregel and Giraph.
Simple — eight lines, one queue, one visited set. Hard to get wrong once you mark-on-enqueue.

Cons

Wrong on weighted graphs — every edge weighs 1, full stop.
Memory grows with the frontier — on a wide graph (high branching factor) the queue can hold most of the next layer at once. Worst case Θ(V).
No notion of 'direction' — BFS explores symmetrically, even if you already know the goal is north-east. A* fixes that with a heuristic.
Order within a level is arbitrary — depends on adjacency-list order, which can surprise debuggers expecting a stable visit order.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

bfs.ts

// BFS on an adjacency list. Returns shortest-path distances
// (in edges) from `start` to every reachable node.
function bfs(adj: Map<string, string[]>, start: string): Map<string, number> {
  const dist = new Map<string, number>();
  const queue: string[] = [start];
  dist.set(start, 0);

  while (queue.length > 0) {
    const node = queue.shift()!;          // dequeue front
    for (const nb of adj.get(node) ?? []) {
      // Mark on enqueue, NOT on dequeue — prevents re-adds.
      if (!dist.has(nb)) {
        dist.set(nb, dist.get(node)! + 1);
        queue.push(nb);                   // enqueue back
      }
    }
  }
  return dist;
}

// To reconstruct the shortest path, store a `parent` map alongside `dist`
// and walk parents back from the target.
// Real-world use: ring buffer / Deque instead of `shift()` (O(1) vs O(n)).

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Why is BFS guaranteed to return the shortest path in an unweighted graph, but not in a weighted one?

question 02 / 03

When should a node be marked as 'seen' so the same node isn't enqueued twice?

question 03 / 03

On a graph with V nodes and E edges (adjacency list), what is BFS's time complexity?

0/3 answered