Breadth first search

Breadth-first search is a simple strategy in which the root node is expanded first, then all the

SEARCH

successors of the root node are expanded next, then their successors, and so on. In general,

all the nodes are expanded at a given depth in the search tree before any nodes at the next

level are expanded.

Breadth-first search is an instance of the general graph-search algorithm (Figure 3.7) in

which the shallowest unexpanded node is chosen for expansion. This is achieved very simply

by using a FIFO queue for the frontier. Thus, new nodes (which are always deeper than their

parents) go to the back of the queue, and old nodes, which are shallower than the new nodes,

get expanded first. There is one slight tweak on the general graph-search algorithm, which is

that the goal test is applied to each node when it is generated rather than when it is selected for

expansion. This decision is explained below, where we discuss time complexity. Note also

that the algorithm, following the general template for graph search, discards any new path to

a state already in the frontier or explored set; it is easy to see that any such path must be at

least as deep as the one already found. Thus, breadth-first search always has the shallowest

path to every node on the frontier