(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
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.
Entry modified Mon Apr 18 09:02:40 2005.
HTML page formatted Wed Oct 26 09:47:25 2005.
Cite this as:
Paul E. Black, "depth-first search", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/depthfirst.html
