Hot-Link Menu in Right-Side Column
Last Updated 6-29-2010
Depth-First search always expands the deepest node in the current frontier of the search tree. The progress of the search is illustrated in Figure DFS-1. The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search "backs up" to the next deepest node that still has unexplored successors:
The unexplored region is shown in white, the frontier in blue, and the explored region is depicted in gray. The arrow is pointing at the node that is currently under expansion.
The depth-first search algorithm is an instance of the graph-search algorithm in Figure Agents-7; whereas breadth-first search uses a FIFO queue, depth-first search uses a LIFO queue. A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent - which, in turn, was the deepest unexpanded node when it was selected.
As an alternative to the Graph-Search-style implementation, it is common to implement depth-first search with a recursive function that calls itself on each of its children in turn.
The properties of depth-first search depend strongly on whether the graph-search or tree-search version is used. The graph-search version, which avoids repeated states and redundant paths, is complete in finite spaces because it will eventually expand every node. The tree-search version, on the other hand, is not complete - for example, in Figure Agents-6, the algorithm will follow the Arad-Sibiu-Arad-Sibiu loop forever. Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node; this avoids infinite loops in finites state spaces but does not avoid the proliferation of redundant paths. In infinte state spaces, both versions fail if an infinite non-goal path is encountered.
Listed below is the pseudocode for the Depth-First Search Algorithm:
Using Figure DFS-2 as a guide, we will begin to develop working code using C++ for a Depth-First Search solution to the Romanian map problem.
As in the solution for the Breadth-First Search we begin by developing a data stucture to contain the information in the following diagram:
However, unlike the Breadth-First solution, the Depth-First solution requires a bit more complexity in the data structure container. In the breadth-first search example, once a node was completed, it was possible to no longer consider that node during the rest of the search. In the Depth-First search, however, we must keep a node "open" during expansion, while we continually expand the children of the node, until we reach the lowest level of the search tree. For this reason, we will use a Class data structure for both the City data structure as well as the PathRecord data structure: