Worked examples — BFS — algorithm, queue-based, O(V+E), shortest path in unweighted graphs

We reuse the parent's engine exactly:

BFS(s):
    dist[s]=0; visited[s]=True; queue=[s]
    while queue:
        u = queue.popleft()          # oldest → smallest dist
        for w in adj[u]:
            if not visited[w]:
                visited[w]=True       # mark at PUSH time
                dist[w]=dist[u]+1
                parent[w]=u
                queue.append(w)

The scenario matrix

Every graph BFS meets falls into one of these case classes. The examples below each tag which cell(s) they cover, and together they hit all of them.

Example 1 — Case A: simple connected, unique shortest path

Steps.

1. d0=0, queue [0]. Why? distance to itself is zero — the ripple's centre.
2. Pop 0; neighbors 1,4 unvisited → d1=1, d4=1, queue [1,4]. Why? both are one hop from source, so level 1.
3. Pop 1; neighbor 2 unvisited → d2=2, queue [4,2]. Why? 1 popped before 4 (FIFO), so its children get processed first, but they still get level 2.
4. Pop 4; neighbor 3 unvisited → d3=2, queue [2,3]. Why? 4 is at level 1, so 3 is level 2 — the 2-edge route wins, exactly as the ring model predicts.
5. Pop 2; neighbor 3 already visited → skip. Why? the visited check kills the longer 3-edge route before it can overwrite.
6. Pop 3; no new nodes. Queue empty → done.

Result: $\{0:0,1:1,4:1,2:2,3:2\}$.

Example 2 — Case B: two equal shortest paths, who discovers first?

Steps.

1. d0=0, queue [0].
2. Pop 0; scan neighbors in list order 1 then 2 → d1=1,parent1=0; d2=1,parent2=0. Queue [1,2]. Why order matters? 1 enters the queue before 2.
3. Pop 1 (FIFO, it's oldest); neighbor 3 unvisited → d3=2, parent3=1. Queue [2,3]. Why parent is 1? 1 reached 3 first because it was dequeued first.
4. Pop 2; neighbor 3 already visited → skip. Why? the tie is already resolved; the second equal path is discarded.

Result: $d3=2$, parent[3]=1. Path reconstructed: 3→1→0, reversed 0,1,3.

Example 3 — Case C: a cycle, don't loop forever

Steps.

1. d0=0, queue [0].
2. Pop 0; neighbors 1,2 unvisited → d1=1,d2=1, queue [1,2].
3. Pop 1; neighbors are 0 (visited) and 2 (visited) → both skipped. Why? the cycle's back-edges hit already-visited nodes and are ignored — this is what stops the infinite loop.
4. Pop 2; neighbors 1(visited),0(visited) skipped, 3 unvisited → d3=2, queue [3].
5. Pop 3; no new. Done.

Result: $\{0:0,1:1,2:1,3:2\}$, terminates cleanly.

Example 4 — Case D: disconnected graph, unreachable = infinity

Steps.

1. Init all dist=∞ except d0=0. Why ∞? it marks "not yet reached"; unreachable nodes keep this value.
2. BFS from 0 reaches 0(0),1(1),2(2). Queue empties.
3. Nodes 3,4 were never pushed → their dist stays ∞. Why? no edge crosses between components; the ripple can't jump the gap.

Result: $\{0:0,1:1,2:2,3:\infty ,4:\infty \}$.

Example 5 — Case E: degenerate inputs (single node, self-loop)

Steps — (a) single node.

1. d0=0, queue [0].
2. Pop 0; adj[0] is empty → no neighbors. Queue empties. Done.
3. Result: $\{0:0\}$. Why fine? BFS on a lone node just labels the source and stops — the base case.

Steps — (b) self-loop 0-0 + 0-1.

1. d0=0, queue [0].
2. Pop 0; scan neighbors: 0 itself → already visited (marked at start) → skip. 1 unvisited → d1=1. Why the self-loop is harmless? 0 was marked visited before the loop, so the edge 0→0 is instantly rejected.
3. Result: $\{0:0,1:1\}$.

Example 6 — Case F: directed graph, one-way edges

Steps.

1. d0=0, queue [0].
2. Pop 0; out-edges 0→1, 0→3 → d1=1,d3=1, queue [1,3]. Why only out-edges? in a directed graph you may only follow arrows in their pointing direction.
3. Pop 1; out-edge 1→2 → d2=2, queue [3,2].
4. Pop 3; no out-edges. Pop 2; out-edge 2→0 → 0 visited, skip. Done.

Result: $\{0:0,1:1,3:1,2:2\}$. Reaching 2 needed the long way 0→1→2 because 0→2 isn't an arrow.

Example 7 — Case G: real-world grid maze (implicit graph)

We use (row,col) as node names; neighbors are computed on the fly (no adjacency list stored).

Steps.

1. d(0,0)=0, queue [(0,0)]. Why implicit? the graph is huge/regular — cheaper to compute the 4 neighbors than store edges.
2. Pop (0,0); neighbors: right (0,1) open→ d=1; down (1,0) is # → blocked. Queue [(0,1)]. Why check walls? walls = missing edges.
3. Pop (0,1); down (1,1) open → d=2; right (0,2) is # skip. Queue [(1,1)].
4. Pop (1,1); right (1,2) → d=3; down (2,1) → d=3. Queue [(1,2),(2,1)].
5. Pop (1,2); down (2,2)=G → d=4. Goal reached.

Result: minimum moves to G = 4. One shortest path: (0,0)(0,1)(1,1)(1,2)(2,2).

Example 8 — Case H: exam twist, multi-source BFS

Steps.

1. d0=0, d4=0, queue [0,4]. Why both at 0? every source is its own zero-distance ripple centre; they all start level 0.
2. Pop 0; neighbor 1 → d1=1, queue [4,1].
3. Pop 4; neighbor 3 → d3=1, queue [1,3].
4. Pop 1; neighbor 2 → d2=2, queue [3,2].
5. Pop 3; neighbor 2 already visited → skip. Why? 2 was reached from source 0's side first, and both sides are equidistant, so the min is locked.

Result: $\{0:0,1:1,2:2,3:1,4:0\}$ — each is distance to nearest source. Node 2 is 2 from either end.

Example 9 — Case I: the trap, BFS on a weighted graph

Steps.

1. BFS ignores weights: pop 0, neighbors 1,2 → d1=1, d2=1 (edge counts).
2. BFS reports cost to 1 = 1 edge, path 0→1, implied cost 10.
3. True cheapest cost = 0→2→1 = 1 + 1 = 2, which uses 2 edges. BFS never considers it because it stops at the first (fewer-edge) arrival.

Result: BFS answer (edges) = 1 → cost 10. Correct answer needs Dijkstra's Algorithm → cost 2.

Recall

Connections

• BFS — main note (the engine we reuse here)
• Connected Components (Case D: loop BFS over every unvisited node)
• Dijkstra's Algorithm (Case I fix: weighted shortest paths)
• 0-1 BFS (weights restricted to 0/1)
• Shortest Path Tree (the parent array from Case B)
• Bipartite Check (BFS by level parity — another scenario)
• DFS — depth-first traversal (contrast: stack, no shortest-path guarantee)
• Graph Representations — adjacency list vs matrix (implicit grid of Case G)