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

Step 0 — What is a graph, really? (nothing assumed)

We will call our starting dot the source and label it $s$ (the letter $s$ just stands for "start" — it is a name, not a number).

Unweighted means every line is the same length — one hop is one hop, no line is "longer" than another. That single assumption is the reason everything below works.

Look at the figure: five dots, some lines, and the source $s$ circled. Right now no dot has a number. Our whole job is to write the fewest-hops number on every dot.

Step 1 — The number we want to compute: $d(v)$

WHY count edges and not something fancier? Because the graph is unweighted — every line costs exactly $1$. So the cost of a path is literally how many lines it uses. Minimising cost = minimising line count.

PICTURE: In the figure below, the source has $d(s)=0$ (you cross zero lines to stand where you already are), and a dot two lines away has $d=2$.

Step 2 — The ripple idea: sort dots into rings

The key claim we will lean on the whole page:

WHY must ring $k+1$ dots be neighbours of ring $k$? Because to reach a ring-$(k+1)$ dot in $k+1$ hops, your second-to-last dot must be reachable in $k$ hops — i.e. it lives in ring $k$. There is nowhere else the shortest path could have come from.

Step 3 — We need a waiting line that respects rings: the queue

The mechanism, term by term: put $s$ in the line. Serve the front dot $u$. For each neighbour $w$ of $u$, if $w$ has never been in the line, put it at the back. Because $u$ (a ring-$k$ dot) entered before any ring-$(k+1)$ dot, the queue always keeps lower rings ahead.

Step 4 — Setting the number the moment we discover a dot

WHY fix it now and never change it? Because $u$ came off the front of a FIFO queue, $u$ has the smallest remaining distance. Any other route to $w$ would pass through some dot whose distance is $\ge d(u)$, so that route is length $\ge d(u)+1$. No route can beat what we just found. This is the heart of correctness.

WHY mark $w$ "visited" at push time (not later)? So the same dot is never queued twice. If two ring-$k$ dots both border $w$, only the first one gets to enqueue it — the second sees "already visited" and skips.

Step 5 — Watch the queue never mix more than two rings

WHY does this stay true? When we serve a ring-$k$ dot $u$, we only ever push its neighbours, which are ring $k$ (already visited → skipped) or ring $k+1$ (pushed to the back). We never create a ring $k+2$ while any ring $k$ remains. So the line drains ring by ring.

Consequence — the payoff: dots leave the queue in non-decreasing order of $d$. Therefore the first time we touch any dot, no smaller distance is still possible. ∎ (This is the shortest-path tree being built one edge at a time.)

Step 6 — Edge & degenerate cases (never leave the reader stranded)

The one-picture summary

This final figure stacks the whole derivation: the source at ring 0, rings colouring outward, the FIFO queue draining lowest-ring-first, and each edge writing $d(u)+1$ on a fresh dot exactly once.

Active Recall

Connections

• 3.5.04 BFS — algorithm, queue-based, O(V+E), shortest path in unweighted graphs (Hinglish) (parent topic)
• DFS — depth-first traversal (the stack-based cousin that dives deep)
• Dijkstra's Algorithm (what to use once edges have weights)
• 0-1 BFS (deque trick for 0/1 weights)
• Graph Representations — adjacency list vs matrix (how neighbours are stored)
• Connected Components (re-run BFS on untouched dots)
• Bipartite Check (colour by ring parity)
• Shortest Path Tree (the tree built by the parent links)