Breadth-First Search

Breadth-first search explores all states at depth $d$ before any state at depth $d+1$. Frontier is a FIFO queue.

Algorithm

``` function BFS(initial, goal): frontier = Queue([(initial, [])]) visited = {initial} while frontier not empty: (state, path) = frontier.dequeue() if state is goal: return path for action in actions(state): next = transition(state, action) if next not in visited: visited.add(next) frontier.enqueue((next, path + [action])) return failure ```

Properties

• Complete: yes (finite branching factor).
• Optimal: yes if step costs are uniform; otherwise no.
• Time: $O(b^d)$ — generates every state up to depth $d$.
• Space: $O(b^d)$ — the frontier alone grows exponentially.

When BFS works well

• Solutions are shallow (small $d$).
• Step costs are uniform.
• The goal is "find any path to a goal," not "find the cheapest path with mixed costs."
• Memory isn't binding.

When it falls down

The space complexity. With $b=10$ and $d=15$, you'd need to store roughly $10^{15}$ states in the frontier — impossible. This is the single largest practical limitation.

Variants

• Bidirectional search: run BFS from both the start and the goal simultaneously. When the two frontiers meet, you have a path. Reduces effective depth to $d/2$, so $b^{d/2}$ instead of $b^d$. Massive speedup when applicable — requires being able to enumerate predecessors of the goal.

In practice

BFS is the right answer for many small puzzles, reachability problems, and shortest-path-on-unweighted-graph queries. For anything where step costs vary or depths are large, you graduate to Dijkstra (uniform-cost) or A* (heuristic-guided).