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 , the branching factor is finite.

Time Complexity

Suppose solution is at depth , worst-case

where is the branching factor.

If solution test happens at expansion time:

Space Complexity

In the worst-case, breadth-first search keeps every node in memory. Thus is it or if the solution test happens at expansion time.

Optimality

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