depth-first search


Also found in: Acronyms, Wikipedia.

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 iterative deepening.
References in periodicals archive ?
Despite these simplifications the depth-first search procedure will not complete on the resulting graph in a reasonable time.
For depth-first search, the software had to offer ways for the user to mark vertices, move from the current vertex to a neighbor of it, and maintain a stack of vertices.
Clearly, it is not the algorithm itself, which, as described previously, is a forward-chaining algorithm with a depth-first search strategy.
Tarjan's algorithm performs a bottom up traversal of the depth-first search tree, identifying inner (nested) loops first.
If the actor has made plans, as he or she might have done in a depth-first search, the first action of the plan is executed.
After carefully studying the properties of depth-first search, we developed a way to generate paths in O(n) time using depth-first search.
John came in one day with this slick biconnectivity algorithm based on what later turned out to be depth-first search, and showed it to me on the blackboard.