Breadth-first search (BFS)

Prerequisites

• Graph representations.
• Queue (FIFO).
• Arrays used as "visited" flags.

The analogy

How it works

Precondition: BFS distances are shortest paths only when every edge counts as 1 (unweighted graph). For weights, use Dijkstra.

Start with one BFS by hand

Graph: 0–1, 0–2, 1–3, 2–3, 3–4 (undirected). Start at 0 with the queue [0]; neighbours are checked in increasing order. Predict, then open "Check".

Finish the picture: the shortest path itself

Store, for each vertex, the vertex that discovered it (its parent).

• Parents. Predict the parent of 3 and of 4.
  Check

  parent(3) = 1 (1 found it first), parent(4) = 3.

• Path to 4. Predict the shortest path from 0 to 4 by following parents backwards.
  Check

  4 → 3 → 1 → 0, reversed: 0, 1, 3, 4. Three edges, matching distance 3.

The rule in plain words

Put the start in a queue with distance 0 and mark it. Repeatedly dequeue a vertex and, for each unmarked neighbour, mark it, set distance = current + 1, and enqueue it.

Mark vertices when they are enqueued, not when dequeued, so nobody enters the queue twice.

The code

Read this code after you have done the BFS by hand. It will make more sense.

void bfs(int adj[][5], int n, int s, int dist[]) {
    int queue[100];
    int head = 0, tail = 0;
    for (int i = 0; i < n; i++) dist[i] = -1;      /* -1 = not discovered */
    dist[s] = 0;
    queue[tail++] = s;
    while (head < tail) {
        int u = queue[head++];                     /* oldest discovered vertex */
        for (int v = 0; v < n; v++)
            if (adj[u][v] && dist[v] == -1) {      /* undiscovered neighbour */
                dist[v] = dist[u] + 1;
                queue[tail++] = v;
            }
    }
}

graph LR
  0((0)) --- 1((1))
  0 --- 2((2))
  1 --- 3((3))
  2 --- 3
  3 --- 4((4))
          

How fast is it?

Each vertex is enqueued and dequeued once, and each adjacency list is scanned once when its vertex is dequeued:

With an adjacency matrix, as in the code above, each dequeue scans a whole row, giving $O(V^2)$.

Common mistakes

• Using a stack instead of a queue, which turns BFS into DFS and loses the shortest-path property.
• Marking vertices on dequeue instead of on enqueue.
• Using BFS distances on a weighted graph.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• BFS explores in layers because its queue processes vertices in the order they were discovered.
• It finds shortest unweighted paths because every vertex is first reached from the layer just before it.
• It runs in $O(V + E)$ on lists because each vertex is enqueued once and each edge is checked a constant number of times.
• Vertices are marked on enqueue because that stops duplicates from entering the queue.
• Parents give the actual path because each parent is one step closer to the start.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is BFS like ripples on a pond?
   Sample answer

   It reaches everything one step away, then two steps, then three, in rings around the start.

2. Walk through BFS from 0 on the graph 0–1, 0–2, 1–3, 2–3, 3–4.
   Sample answer

   Visit 0; enqueue 1 and 2 (distance 1); 1 adds 3 (distance 2); 2 adds nothing new; 3 adds 4 (distance 3). Order 0, 1, 2, 3, 4.

3. Why does the code set dist[v] when enqueuing rather than when dequeuing?

   A good answer mentions vertex 3 in the example.

   Sample answer

   Setting it at enqueue marks v as discovered at once, so when 2 also sees 3, it is skipped and 3 enters the queue only once.

4. So what is BFS, in one sentence?
   Sample answer

   A queue-based traversal that explores a graph layer by layer from a start vertex.

5. Why does BFS give shortest paths in unweighted graphs but not in weighted ones?

   A good answer says what a "layer" counts.

   Sample answer

   Layers count edges. With weights, a path with more edges can be cheaper, so the first time BFS reaches a vertex is not necessarily the cheapest way.

6. What are BFS's time and space costs?
   Sample answer

   $O(V + E)$ time on adjacency lists ($O(V^2)$ on a matrix) and $O(V)$ extra space.

7. How do you recover the actual shortest path, not just its length?
   Sample answer

   Store each vertex's parent when it is discovered, then follow parents from the target back to the start and reverse.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the matrix-versus-list cost and the marking detail. I'd keep the ripple analogy, the 5-vertex example with layers, and "queue, layers, shortest path in edges, $O(V + E)$".

External resources

• VisuAlgo: DFS and BFS: run BFS on your own graph and watch the queue.
• GeeksforGeeks: BFS: code and applications.
• Wikipedia: Breadth-first search: history, analysis and uses.
• MIT OCW 6.006: lecture on BFS.

Videos

• YouTube search: BFS explained: pick a walkthrough with the queue drawn.