Basic search methods - depth-first, breadth-first

In section 2 we described the process of generating a search tree, in this section we will give a more precise description of this process.


These are the basic elements of a problem-solving process, but the order in which nodes are to be expanded is still left open. We may choose, for instance, to search one entire branch of the tree before examining nodes in the other branches. Alternatively, we may decide to expand all nodes that are on the same level, in different branches. The first option would result in what is called a depth-first  search: the most recently generated node gets expanded first. In a breadth-first  search, the second option, nodes are expanded in the order in which they are generated.