depth-first search

algorithm A graph search algorithm which extends the

current path as far as possible before backtracking to the

last choice point and trying the next alternative path.

Depth-first search may fail to find a solution if it enters a

cycle in the graph. This can be avoided if we never extend a

path to a node which it already contains.

Opposite of breadth first search. See also iterativedeepening.

(1995-04-19)