Depth-first search

From AMS Glossary
Jump to: navigation, search

depth-first search

A search algorithm that extends the current path as far as possible before backtracking to the last choice point and trying the next alternative path.

Depth-first search generally reaches a satisfactory solution more rapidly than breadth first, an advantage when the search space is large. However, unlike breadth first, it does not guarantee that the optimal solution has been found.
Compare breadth-first search.

Personal tools