# 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*, *Cupif-Giannini tree traversal*.

*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. Many algorithms using depth-first search (Java) using Sedgewick and Wayne "Algorithms" 4th edition.
## More information

Lecture notes from Design and Analysis of Algorithms on Breadth-first search and depth-first search.

From xkcd 761 by Randall Munroe. 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 15 October 2021.

HTML page formatted Fri Oct 15 16:48:46 2021.

Cite this as:

Paul E. Black, "depth-first search", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 15 October 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/depthfirst.html