(algorithm)
Definition: (1) Any search algorithm that considers outgoing edges (children) of a vertex before any of the vertex's siblings, that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first. This is easily implemented with recursion. (2) An algorithm that marks all vertices in a directed graph in the order they are discovered and finished, partitioning the graph into a forest.
Also known as DFS.
Specialization (... is a kind of me.)
preorder traversal, in-order traversal, postorder traversal.
See also breadth-first search, best-first search.
Note: Depth-first search doesn't specify if a vertex is considered before, during, or after its outgoing edges or children. Thus it can be preorder, in-order, or postorder traversal.
Author: PEB
Lecture notes from Design and Analysis of Algorithms on Breadth-first search and depth-first search. An animation (Java).
An early mention of depth-first search:
C. Cordell Green and Bertram Raphael, The use of theorem-proving techniques in question-answering systems, Proc. 1968 23rd ACM national conference, pages 169-181, 1968.
Uses just "depth-first search" in the body (page 5), but contrasts depth-first with breadth-first search in a footnote.
An earlier description of what we would call depth-first search with pruning of infeasible solutions.
Solomon W. Golomb and Leonard D. Baumert, Backtrack Programming, Journal of ACM, 12(4):516-524, Oct 1965.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 8 January 2008.
HTML page formatted Tue Jan 22 09:34:08 2008.
Cite this as:
Paul E. Black, "depth-first search", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 8 January 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/depthfirst.html
