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

WHAT is BFS?

WHAT it produces: a level-order visiting sequence, a BFS tree, and (for unweighted graphs) shortest-path distances from the source.
WHAT data structures: a queue (the frontier) + a visited/dist array.

WHY a queue gives us "rings"

If we used a stack (LIFO) instead, we'd dive deep first — that's DFS, and it does not give shortest paths.

HOW the algorithm runs (derivation from first principles)

We want: for every node $v$ , the minimum number of edges $d(v)$ from source $s$ .

Claim we build on: if we already know all nodes at distance $k$ , then every node at distance $k+1$ is a neighbor of some distance- $k$ node, and is not yet visited.

Derivation of the steps:

Start: $d(s)=0$ . Put $s$ in queue. (Why? distance to itself is 0.)
Pop a node $u$ (the oldest in queue → smallest distance). (Why oldest? to keep level order.)
For each neighbor $w$ of $u$ that is unvisited: it's reached for the first time, so $d(w)=d(u)+1$ . Mark visited, push $w$ . (Why mark now, at push time? So it's never queued twice.)
Repeat until queue empty.

BFS(s):
    dist[s] = 0
    visited[s] = True
    queue = [s]
    while queue not empty:
        u = queue.popleft()          # FIFO → smallest dist first
        for w in adj[u]:
            if not visited[w]:
                visited[w] = True     # mark at enqueue time!
                dist[w]    = dist[u] + 1
                parent[w]  = u        # for path reconstruction
                queue.append(w)

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

WHY shortest path? (proof sketch)

Worked Examples

Worked example Example 1 — shortest path on a small graph

Graph (undirected): 0-1, 0-2, 1-3, 2-3, 3-4. Source = 0.

step	pop	queue after	dist updates
init	—	[0]	d0=0
1	0	[1,2]	d1=1, d2=1
2	1	[2,3]	d3=2 (via 1)
3	2	[3]	3 already visited → skip
4	3	[4]	d4=3
5	4	[]	done

Result: distances $\{0:0,1:1,2:1,3:2,4:3\}$ . Why d3=2 not 3? Node 3 was discovered from level-1 node 1 first, so the shortest path 0→1→3 (length 2) is captured, not 0→2→3 (also 2) or longer.

Common Mistakes (Steel-manned)

Recall Feynman: explain to a 12-year-old

Pretend the graph is a metro map and you start at one station. You first write "0" on your home station. Then you visit every station one hop away and write "1". Then every new station one hop from those gets "2", and so on. You always finish all the lower numbers before any higher number — like checking everyone on floor 1 before going to floor 2. The number you wrote is the fewest hops to that station. The "queue" is just a line of stations waiting their turn — first in line goes first.

Active Recall

What data structure drives BFS and why?

A FIFO queue — it serves nodes in arrival order, guaranteeing level-by-level (distance-sorted) exploration.

Why does BFS find shortest paths in unweighted graphs?

Nodes are dequeued in non-decreasing distance order, so the first time a node is reached it's via the fewest edges.

What is the time complexity of BFS and why?

O(V+E)

— each vertex enqueued/dequeued once (

V

), each edge scanned once (

E

); separate loops so we add.

When should you mark a node visited?

At enqueue (push) time, to prevent the same node being added to the queue multiple times.

Why is BFS wrong for weighted shortest paths?

BFS minimizes edge count, not total weight; use Dijkstra for weighted (non-negative) graphs.

How do you reconstruct the shortest path itself?

Store parent[w] when discovering w, then walk parents from target back to source and reverse.

What does the queue contain at any moment during BFS?

Nodes of at most two consecutive levels

k

and

k+1

, with level-

k

nodes ahead.

DFS vs BFS for shortest path — which and why?

BFS; DFS uses a stack (LIFO) and dives deep, so first arrival is not guaranteed shortest.

Connections

DFS — depth-first traversal (stack/recursion, used for cycles, components, topological order)
Dijkstra's Algorithm (BFS generalized to weighted graphs via priority queue)
0-1 BFS (deque trick for 0/1 edge weights)
Graph Representations — adjacency list vs matrix (affects the $E$ in $O(V+E)$ )
Connected Components (run BFS from each unvisited node)
Bipartite Check (BFS 2-coloring by level parity)
Shortest Path Tree (the parent pointers form this tree)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek talaab me patthar phenka — paani me rings (lehrein) bahar ki taraf failti hain: pehle 1 step door ke points, phir 2 step door, phir 3. BFS bilkul yahi karta hai graph me. Source node se start karke, pehle uske saare direct padosi (level 1), phir unke padosi (level 2), aise hi ring-by-ring explore karta hai. Isiliye jab BFS kisi node tak pehli baar pahunchta hai (unweighted graph me), wahi shortest path hota hai — kam se kam edges wala raasta.

Iska engine hai ek FIFO queue. Queue me jo pehle aata hai wahi pehle nikalta hai, isliye chhoti distance wale nodes pehle process hote hain — yahi level-order ka raaz hai. Agar tum stack (LIFO) use karte to deep chale jaate, aur woh DFS ban jaata, jo shortest path guarantee nahi deta. Ek important rule: node ko visited mark queue me daalte waqt karo, pop karte waqt nahi — warna same node baar-baar queue me ghus jaayega aur galat ho jaayega.

Complexity $O(V+E)$ hai: har vertex ek hi baar queue me aata-jaata hai ( $V$ ), aur har edge ek baar scan hota hai ( $E$ ). Yaad rakho — add hota hai, multiply nahi, kyunki vertex ka kaam aur edge ka kaam alag-alag loops me hote hain.

Last cheez — BFS sirf unweighted (ya har edge ka weight 1) graph me shortest path deta hai. Agar edges ke alag-alag weights hain, to BFS galat answer dega kyunki woh sirf edges ginta hai, weight nahi. Tab Dijkstra use karo. Path waapas nikalne ke liye parent[] store karo aur target se source tak peeche chalte jao, phir reverse kar do.

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

WHAT is BFS?

WHY a queue gives us "rings"

HOW the algorithm runs (derivation from first principles)

WHY shortest path? (proof sketch)

WHY is it $O(V+E)$ ?

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections