depth-first search

(redirected from Depth-first)

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 ?
The search amounts to a depth-first traversal of the graph.
Techniques such as Random Walk [5], Restricted Random Walk [6], Breadth-First Search [7], Intelligent BFS [8], Depth-First Search [9], Adaptive Probabilistic Search [10], Blackboard Resource Discovery Mechanism [11] are explained briefly in the following subsections.
DMAIC Six Sigma may still be used during depth-first plunges into the system architecture analysis and for 'back end' Six Sigma processes; DFSS provides system design processes used in front-end complex system designs.
On this graph the user can run the depth-first search and the breadth-first search algorithm either stepwise or with the result shown dynamically while the graph changes.
We can construct a spanning tree via a depth-first or breadth-first graph traversal.
As shown in figure 8, Upstart-using the depth-first construction strategy-continues down one branch until it is complete.
For structural problems, the classic sequential methods for depth-first searches along undirected graphs were studied and some limitations for their use in networks of workstations were individualized.
Another is depth-first ordering, the reverse of the order in which nodes are last visited in a preorder traversal of the flow graph [Aho et al.
Translating Hierarchical Instructions into Linear Text: Depth-First Versus Breadth-First Approaches," by Hans Hoeken, Marieke Mom, and Fons Maes, clearly articulates and carefully dissects a complex problem faced by many technical communicators.
In depth-first search, an actor would make plans for the future by devising chains of alternatives.
Moon [4] has described a modification that achieves an approximately depth-first graph traversal.
We assume that the reader is familiar with depth-first search [Hopcroft and Tarjan 1973] (abbreviated DFS) and depth-first search trees.