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)