Breadth-First Search (BFS)

The conservative search — sweep level by level. Guaranteed shortest path, but Open explodes exponentially

The Simplest Explanation

BFS is the conservative tourist. Before walking any street two blocks away, it finishes inspecting every corner within one block. It expands outward from the start in perfect rings.

The entire algorithm is the general generate-and-test loop with one line deciding its personality:

Add new nodes at the tail of Open → Open behaves like a queue (FIFO) → explore nodes in the order they were generated.

Remember This

BFS = add to tail = FIFO = level by level = first time you touch the goal, the path IS shortest.

The Algorithm

Identical to DFS except for step 6:

Pick the first pair (n, parent) from Open
If GoalTest(n) passes → return path
Move n to Closed
neighbors = RemoveSeen(MoveGen(n), Closed)
newPairs = MakePairs(neighbors, n)
Append newPairs to Open (Open ++ newPairs)

Because children enter the queue after all older candidates, BFS processes every node at distance $k$ before any node at distance $k+1$ .

Here BFS has finished levels 0–1 (S, A, B) and is sweeping level 2 (D, E, F on Open). It will not look at anything deeper until this ring is done.

Interactive Trace

Same graph as the DFS page — switch between DFS and BFS and watch how differently they treat the same Open list:

Blind Search TraceStep 0 / 4

Current

On Open (frontier)

Closed (visited)

Path to Goal

Initialize: Open = [(S, nil)], Closed = []. S is the start state.

Open (stack — add at head)

[(S, ·)]

Closed

[]

Key Observations

BFS sweeps: S, then A/B/D, then C/E/G — never diving until a full ring is done.
It finds the shortest path: S → D → G (length 2), where DFS found length 3.
Duplicates appear on Open: with Closed-only pruning, B and D sit on Open multiple times via different parents. Only the "no duplicates" policy prevents this.
Open grows explosively: by step 5, Open holds most of the graph.

Analysis

Assume constant branching factor $b$ and goal at depth $d$ .

Time Complexity

Scenario	Nodes inspected
Best case (goal at depth d, last of its level)	$O(b^{d})$
Worst case	$O(b^{d})$
Average	$\approx O(b^d)\cdot\frac{b+1}{2(b-1)}$

Compared with DFS's average $\approx O(b^{d/2})$ , the ratio is roughly $\frac{b+1}{b-1}$ : for $b = 10$ , BFS inspects only about $\frac{11}{9} \approx 1.2\times$ more nodes. Time is comparable — space is not.

Space Complexity — BFS's Weakness

Every node at the current level sits on Open simultaneously:

$|\text{Open}| = O(b^d) \quad \text{— exponential!}$

At depth 12 with $b = 10$ , that's a trillion nodes in memory. BFS dies of memory exhaustion long before it dies of time.

Why BFS Guarantees Shortest Paths

Nodes leave Open in non-decreasing distance from start (each level is fully queued before the next). So the first goal node dequeued has minimal distance. No extra bookkeeping needed — it's free.

Property	Value
Shortest path guaranteed?	Yes (unweighted edges)
Complete?	Yes — if any finite-length path exists, BFS finds it
Optimal with edge costs?	No — use Dijkstra / A* instead
Space	$O(b^d)$ — usually the killer

Robustness Against Cycles

In the lecture's tiny example, when all pruning was removed (even the Closed list):

DFS looped forever (S → A → C → B → S → ...)
BFS still found the goal — because it processes level by level, cycles only add duplicate entries; the frontier keeps advancing outward

This makes BFS more forgiving when loop checking is imperfect.

QuizWhy is BFS guaranteed to find a shortest path?

QuizDFS and BFS both take O(b^d) time. What is their practical ratio?

QuizWithout ANY pruning (no Closed list), which algorithm survives a cyclic state space?