# depth-first search

(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*, *Schorr-Waite graph marking algorithm*.

*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*.

*
** [CLR90, pages 477-485]*

Author: PEB

## Implementation

Algorithms and Data Structures' explanation and implementation (Java and C++) for undirected graphs.
## More information

Lecture notes from Design and Analysis of Algorithms on Breadth-first search and depth-first search. An animation (Java).

From xkcd by Creative Commons Attribution-NonCommercial 2.5 License.

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.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 6 July 2010.

HTML page formatted Tue May 6 13:48:55 2014.

Cite this as:

Paul E. Black, "depth-first search", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 6 July 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/depthfirst.html