(algorithm)
Definition: (1) Any search algorithm that considers outgoing edges of a vertex before any neighbors of the vertex, 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.
See also breadth-first search, best-first search.
Note: [CLR90, pages 477-485]
Author: PEB
Laboratory Resources on Search and Game Playing, Lecture notes on Uninformed Search, Lecture notes from Design and Analysis of Algorithms on Breadth-first search and depth-first search. A demonstration.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black (paul.black@nist.gov).
Entry modified Fri Dec 17 12:23:34 2004.
HTML page formatted Fri Dec 17 14:50:32 2004.
This page's URL is http://www.nist.gov/dads/HTML/depthfirst.html
