...search
The predicate append/3 is standard and gather/2 has to be a way of collecting all the successors of a given node. The predicate goal_state/1 succeeds once a goal state is found. The use of write/1 is simply to show the order of search.

As a very optional suggestion, consider how you might do this using the built-in predicate bagof/3.
...needed
Warning: this is not what the algorithm shown in figure 5 does. For purposes of showing the similarity between depth-first and breadth-first search, the algorithm for depth-first search calculates all the successors for a node at one go.
...memory
Consider the amount of information needed to be stored during the computation in the running example where we search to a depth of three.

Depth-first search will only need to keep around a maximum of 3 nodes as it only has to `remember' the path from the root node to the current position. On the other hand, breadth-first search will need to keep around up to 9 nodes when searching at the depth of three.

The figure, for depth-first search is usually given as (the depth of the tree being searched) whereas the figure for breadth-first search is given as where is the branching rate (a measure of how many direct successors a node has) and the depth of the tree.

In the example, as is usually the case, the branching rate varies. It is between 2 and 3. If we take it as 3 then we get .

paul@comp.lancs.ac.uk
Tue Jan 9 10:51:07 GMT 1996