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.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
Depth-First Search. Depth-first search (DFS) is an algorithm that explores a tree or graph data structure.
Geffner, "Learning depth-first search: a unified approach to heuristic search in deterministic and non-deterministic settings, and its application to MDPs," in Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS06),D.Long, S.
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.
This is understandable for a method based on depth-first search. Improved word-ordering heuristics might reduce the fraction of such cases.
In depth-first search, an actor would make plans for the future by devising chains of alternatives.
Literature [13] presents an approach that the Depth-First search is applied to generate minimal cut sets.
On the basis of HAC-tree, we propose a noncandidate pruning depth-first search algorithm (NCP-DFS) for searching top-k relevance score documents recursively.
This algorithm uses depth-first search, a systematic way of exploring a graph and visiting each vertex and edge.