IThm> 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)