With the same tree as for depth-first search, breadth-first search proceeds quite differently.
We examine all successor states at the same depth before going deeper.
To search for a winning state, we start with the root node (a). We evaluate all the immediate successor states (nodes b, c and d) before looking at the next level -which consists of nodes e, f, g, h, i, j, k, l and m.
Again, we represent this information as an ordered set of nodes that await exploration.
Here, representing this information as a Prolog list, we start with [a] and produce [b,c,d].
We now take the subtree rooted at node b and expand this -resulting in a need to replace node b by nodes e, f and g. We now remember that we wish to expand node c next.
This is where the difference between breadth-first and depth-first search shows up. With depth-first search, we wanted to look at all the nodes below node b before looking at node c -with breadth-first search, we want to look at nodes b, c and d before looking deeper into the tree.
We have to replace node b with its successors -but we do this by placing them at the end of the list.
Our data structure becomes [c,d,e,f,g] and we continue by choosing to derive the successor states for node c -resulting in [d,e,f,g,h,i,j] (remember that we keep on removing the node from the front of the list in order to derive its successors).
The order of search for the winning state using breadth-first
search
is shown in figure 4.
