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 {iterATive deepening}. (1995-04-19)