depth-first search

A graph-traversal strategy that proceeds along a path from a given vertex as deeply into the graph as possible before backtracking. That is, after visiting a vertex, a DFS visits, if possible, an unvisited adjacent vertex. If the traversal reaches a vertex that has no unvisited adjacent vertices, it backs up and then visits, if possible, an unvisited adjacent vertex. See also breadth-first search.

The DFS strategy has a simple recursive form:

DFS(v)

// Traverses a graph beginning at vertex v by using a

// depth-first search: Recursive version.



Mark v as visited

for (each unvisited vertex u adjacent to v)
    DFS(u)

A method of searching a tree that always travels down one particular branch as far as it can before trying another. For example, the following tree:

     A
   / | \
  B  E  F
 / \   /|\
C   D G H I

will be searched in alphabetical order, if a depth-first search is performed on it (searching leftmost branches first).

In agenda-based searching, that corresponds to the following steps:

• Add the first node to the agenda (in this case, A).
• Examine the first node on the agenda to see if it is the required item.
• Otherwise, expand the node (find all its children), and add those children to the beginning of the agenda.
• Repeat the second and third steps until the goal is reached.

The fact that the nodes are always added to the beginning of the agenda is what makes this a depth-first search; all the children of a node are examined before its siblings are. Contrast this to breadth-first search.

The advantages to depth-first search (over breadth-first search) is that it takes less memory, and therefore is less likely to fail. The disadvantages are that it takes longer, and will not always find the shortest path. Also, if the tree has loops in it (and is thus actually a graph, not a tree), then depth-first search can get stuck in a loop. DFS can also only deal with finite trees.