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

WHAT: a queue. The discipline: FIFO (First-In-First-Out). WHY it matters: nodes added earlier (closer to $s$) leave earlier, so pops come out sorted by distance — that is exactly the "ring by ring" order from the parent note's stone-in-water picture.

$d(s)=0$. WHY: distance counts edges walked, and you walk zero edges to stay where you start. This seeds every other distance: everything else is measured relative to this $0$.

It is DFS. It does not guarantee shortest paths, because a stack serves the newest node, so it plunges deep before finishing a level — the first arrival at a node may be via a long detour, not the fewest edges.

Queue trace (mark visited at push):

Answer: $d_0=0,d_1=1,d_2=1,d_3=2,d_4=3$. WHY $d_3=2$: node 3 is first discovered from level-1 node 1, so it lands on level 2 — the route 0→1→3 (2 edges) is captured, and node 2 (also level 1) finds 3 already visited and skips it.

Parents from the trace: $\text{parent}[1]=0,\text{parent}[2]=0,\text{parent}[3]=1,\text{parent}[4]=3$. Walk backward from 4: $4\to 3\to 1\to 0$. Reverse: 0, 1, 3, 4 (length 3 edges = $d_4$). ✓ WHY backward: each parent points one step toward the source along the BFS tree, so chaining parents is guaranteed to be a shortest route. See Shortest Path Tree.

BFS on the implicit grid graph: the distance to $(r,c)$ equals the fewest unit moves. In an open grid with only U/D/L/R, that is the Manhattan distance $|r-0|+|c-0|$. For $(2,2)$: $2+2=4$ moves. WHY BFS works here: every move costs exactly 1 (unweighted), so first arrival = shortest — no adjacency list needed, neighbors computed on the fly. See Graph Representations — adjacency list vs matrix.

(a) Each vertex is pushed at most once → at most $6$ enqueues. (b) When a vertex is popped, we scan its out-edges once; summed over all vertices that is every directed edge once → $9$ edge scans. (c) $O(V+E)=O(6+9)=O(15)$, i.e. linear $O(V+E)$. WHY add, not multiply: the vertex loop and the edge scan are the same pass, not nested — you don't re-scan all edges for each vertex.

No. The invariant: the queue always holds at most two consecutive levels $k$ and $k+1$, with all level-$k$ nodes ahead of level-$k+1$ nodes. A later state $[3,3,3,2]$ puts a level-2 node behind level-3 nodes and spans no smaller level — impossible, because a level-2 node must have been dequeued before any level-3 node was reached. WHY this matters: this ordering is precisely what makes pops non-decreasing in distance, which is the whole proof of shortest-path correctness.

Node 6 is never reached, so it is never pushed and visited[6] stays false. Conventionally $d_6=\infty$ (or a sentinel like $-1$). WHY: BFS only explores nodes connected to $s$. To cover every node you run BFS again from each still-unvisited node — this is exactly how Connected Components are enumerated.

$d_0=0$ (A), $d_1=1$ (B), $d_2=1$ (B). Now check edge 1-2: both are colored B — same color across an edge. So the 2-coloring fails; the triangle is not bipartite. WHY parity coloring works: in a bipartite graph every edge joins an even level to an odd level. An odd cycle (length 3 here) forces two same-level neighbors to be adjacent, which BFS detects. See Bipartite Check.

BFS ignores weights: it sees 0→1 as 1 edge, so it "reports" node 1 at edge-distance $1$. But the cheapest cost is 0→2→1 $=1+1=2$, versus direct 0→1 $=5$. So the cheapest total cost is $2$. WHY BFS is wrong here: BFS minimizes number of edges, and fewer edges (0→1, one edge) is not cheaper. Use Dijkstra's Algorithm for non-negative weights, or 0-1 BFS if every weight is 0 or 1.

Seed the queue with both sources at distance 0: push 0 and 4 first, $d_0=d_4=0$. From 0: $d_1=1$. From 4: $d_3=1$. Then $d_2=\min (d_1,d_3)+1=1+1=2$ seconds. WHY multi-source works: initializing the queue with several 0-distance nodes makes BFS expand rings from all of them simultaneously; each node's distance is to its nearest source — the FIFO order still guarantees non-decreasing distances.

Claim: if $x$ is dequeued before $y$, then $d(x)\le d(y)$. Proof by the FIFO + push-rule. A node's distance is fixed when it is pushed by its popped parent: $d(\text{child})=d(\text{parent})+1$. Process parents in dequeue order $u_1,u_2,\dots$ with $d(u_1)\le d(u_2)\le \dots$ (induction hypothesis). Children of $u_i$ get distance $d(u_i)+1$ and are pushed in that same order, so they sit in the queue sorted by parent distance. Since FIFO preserves push order, the next batch dequeued is again non-decreasing, and each child's distance $d(u_i)+1\ge d(u_i)=$ its parent's — never smaller than anything already dequeued. Hence the global dequeue order is non-decreasing in $d$. ∎ Consequence: the first time a node is reached, no route of fewer edges exists — that is the shortest-path guarantee.

From Exercise 2.1: $d=\{0,1,1,2,3\}$. The maximum is $3$, achieved by node 4. WHY it's a legitimate BFS output: a single BFS from $s$ gives all $d(v)$ at once, so the eccentricity of $s$ is just ${\max }_{v}d(v)$ — no extra work.

Method: delete $x$ from the graph (skip it in every neighbor loop, treat it as always-visited), then run one ordinary BFS from $s$. Read $d(t)$; if $t$ unreached, no valid path exists. WHY correct: removing $x$ makes every route BFS can find automatically avoid $x$, and BFS on the reduced graph still returns fewest edges among the allowed routes. Complexity: still $O(V+E)$ — one BFS pass, marking $x$ visited up front costs $O(1)$.

A grader could hand you any of these and the pattern is the same: BFS lays down rings of equal distance, the queue keeps the rings in order, and the first time you touch a node is the cheapest (in edges) you'll ever touch it. Everything past L2 is just noticing which problems secretly reduce to "count rings from a source": components, bipartite parity, multi-source fires, forbidden-node paths. If weights appear, BFS steps aside for Dijkstra.