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

Before you can believe that idea, you must be fluent in the tiny alphabet it is written in. This page builds every symbol, word, and picture the parent note silently assumes — in the exact order they depend on each other. Nothing is used before it is drawn.

Parent note: BFS (main note).

1. What is a graph? (the dots-and-strings picture)

The picture: think of a metro map. Each station is a vertex (dot); each rail between two stations is an edge (string).

Why the topic needs it: BFS is a graph traversal — the whole algorithm is about walking dots along strings. Without the dots-and-strings picture, every later symbol is meaningless.

2. Symbols $V$ and $E$ — counting the dots and strings

The picture: in the graph above, count the dots → that is $V$; count the lines → that is $E$.

Why the topic needs it: the parent note's headline speed is $O(V+E)$. That phrase is nonsense until you know $V$ counts dots and $E$ counts strings. We build $O(\dots )$ itself in Section 8.

3. Neighbor and degree — who is one string away

The picture: stand on dot $0$. Everyone you can reach in one hop is a neighbor. The count of those people is your degree.

Why the topic needs it: BFS, when it "visits" a dot, looks at every neighbor. And the total edge-scanning work is the sum of all degrees — the reason $E$ appears in the running time (Section 8).

4. The source $s$ and distance $d(v)$

The picture: write a number on each station equal to how many rails you crossed to get there from home. Those numbers form the rings in the core idea.

Why the topic needs it: the entire promise of BFS is "I will compute $d(v)$ for every $v$." Every ring in Section 1's intuition is the set of all dots with the same $d$ value. The word level = the set of all dots at one distance value.

5. The queue — a line where the first to arrive is the first to leave

The picture: a queue at a ticket counter. Person A arrives first, stands in front; B stands behind A. A is served first.

The two operations we use:

• append(x) — put $x$ at the back of the line.
• popleft() — remove and return the person at the front.

Why the topic needs it — and why a queue, not a stack: we need dots to come out sorted by distance. If we always add the source first, then its ring-1 dots, then ring-2, the FIFO rule serves all of ring 1 before any of ring 2 — because they lined up earlier. That is precisely the "rings" behaviour. A stack (Last-In-First-Out) would serve the newest dot first, diving deep — that gives DFS — depth-first traversal, which does not produce shortest paths.

6. Visited set and parent array — memory tags

The picture: as ripples spread, draw a little arrow on each newly-wet dot pointing back to the ripple that reached it. Follow those arrows all the way back and you retrace the shortest route home. Those arrows form the Shortest Path Tree.

Why the topic needs it: visited guarantees the "each vertex once" rule that makes BFS fast; parent lets us reconstruct the actual path, not just its length (parent note's Example 2).

7. Storing the strings: the adjacency list

The picture: a phone book. Each dot is a name; next to it is the list of its direct contacts.

For the parent's graph 0-1, 0-2, 1-3, 2-3, 3-4:

Why the topic needs it: the inner loop for w in adj[u] walks exactly this list. Choosing a list (vs a full grid/matrix) is why edge work totals $E$, not $V^2$ — see Graph Representations — adjacency list vs matrix.

8. Big-O: the symbol $O(V+E)$

Why it is a sum (not a product): BFS does two separate jobs:

1. Handle each dot once → about $V$ units of work.
2. Look at each string once → about $E$ units of work.

$T=O(\underset{\text{dots handled once}}{\underbrace{V}}+\underset{\text{strings scanned once}}{\underbrace{E}})$

The edge work is ${\sum }_v\mathrm{deg}(v)=2E$ (from Section 3), and constants drop inside $O(\cdot )$, leaving $E$. Because the loops run one after another, not nested, we add. A nested "check every string for every dot" would multiply, giving the slower $O(V\cdot E)$ — BFS avoids that by using the adjacency list.

Prerequisite map

Read it bottom-up: dots-and-strings feed everything; the queue plus distances plus tags plus the adjacency list all pour into the final claim — BFS explores in rings.

Equipment checklist

Cover the right side and answer aloud. If any tag catches you, reread its section.

Connections

• Parent: BFS main note
• DFS — depth-first traversal (the stack/LIFO cousin)
• Dijkstra's Algorithm (BFS generalized to weighted graphs)
• 0-1 BFS (deque trick for 0/1 weights)
• Graph Representations — adjacency list vs matrix (why edge work is $E$)
• Connected Components · Bipartite Check · Shortest Path Tree