Breadth-First Search

search

Definition

Breadth-First Search

Breadth-first search is about expanding the shallowest unexpanded node. The frontier is a FIFO queue, i.e., new successors go at the end.

Properties

Completeness

Breadth-first search is completes since $b$, the branching factor is finite.

Time Complexity

Suppose solution is at depth $d$, worst-case

$$1+b+b^2+b^3+\cdots +b^d=O(b^d)$$

where $b$ is the branching factor.

If solution test happens at expansion time:

$$1+b+b^2+b^3+\cdots +b^3+b^{d+1}=O(b^{d+1})$$

Space Complexity

In the worst-case, breadth-first search keeps every node in memory. Thus is it $O(b^d)$ or $O(b^{d+1})$ if the solution test happens at expansion time.

Optimality

Breadth-first search is optimal if the cost per step is $=1$. Generally speaking, it is not optimal.