We have now shown a way in which depth-first and breath-first search can be seen in terms of how a list of states awaiting expansion is processed.
Figure 5 shows two Prolog programs: one that traverses
some representation of a tree in a depth-first manner and the other
which is a very similar program for breadth-first
search
.
Note that the only difference in the code is in the order of the arguments to append/3. Both programs can be seen as search utilising an explicit agenda of nodes that will need to be expanded.
We illustrate depth-first search using an explicit agenda in figure 6 and breadth-first search using an agenda in figure 7.
