Breadth-first search (FIFO queue)

Level by level

Breadth-first search (BFS) explores *all* states at depth $n$ before *any* state at depth $n+1$. It sweeps outward from the start in concentric shells, and that discipline buys a guarantee: the first time BFS reaches the goal, it has reached it by a path with the fewest arcs — the shortest path in number-of-moves.

The two lists and the FIFO queue

BFS keeps two collections:

- OPEN — discovered-but-not-yet-expanded states, held as a queue (first-in, first-out). New children are added to the back; the next state to expand is always taken from the front. - CLOSED — states already expanded, so they are never processed twice.

The FIFO discipline is the *entire* reason BFS is breadth-first: a state discovered earlier is always expanded earlier, so the search finishes an entire depth level before descending. The algorithm:

1. Put the start state on OPEN.
2. Take a state off the front of OPEN. If it is the goal, stop and reconstruct the path (follow parent pointers).
3. Otherwise move it to CLOSED and add each child not already on OPEN or CLOSED to the back of OPEN.
4. Repeat until OPEN is empty (failure) or the goal is found.

The cost: memory

BFS's price is space. At depth $n$ the OPEN queue can hold $O(B^n)$ states — the whole frontier at once. With $B = 10$, depth 10, that is $10^{10}$ states in memory. BFS is therefore optimal-in-moves but memory-hungry; on deep problems you reach for depth-first or iterative deepening (next lesson).

Worked example — the graph below

Take this small directed graph (children listed in expansion order):

A → B, C
B → D, E
C → F
D → F
E → (none)
F → (none)

Searching from A to F, BFS expands by level: first A (level 0); then its children B, C (level 1); then B's children D, E and C's child F (level 2). The moment F comes off the front of the queue we stop. Reconstructing parents gives the path A → C → F — two arcs, the shortest possible (the route through B and D would be three arcs). Along the way BFS *expanded* 5 nodes (A, B, C, D, E) before pulling F. The runnable cell below reproduces exactly this.