Concepts

Depth-First Search

Also Known As DFS

Algorithm

Citation Formats

General Reference

Computing Atlas. "Depth-First Search." Accessed August 30, 2026. https://dev-computing.interactiveatlas.org/concepts/depth-first-search.

APA Style

Computing Atlas. (n.d.). Depth-First Search. Retrieved August 30, 2026, from https://dev-computing.interactiveatlas.org/concepts/depth-first-search

BibTeX

@misc{computingatlas-depth-first-search,
  author = {Computing Atlas},
  title = {Depth-First Search},
  year = {2026},
  url = {https://dev-computing.interactiveatlas.org/concepts/depth-first-search},
  note = {Accessed August 30, 2026}
}

Depth first search is an algorithm for traversing or searching tree and graph data structures. Starting at a chosen root node, it explores as far as possible along each branch before backtracking, typically using a stack, explicit or via recursion, to track the path and visited nodes.

Facts

Origin Year

1972 1

Maze-solving precursors date to the 19th century (Tremaux's algorithm), but DFS was formalized as an algorithmic technique for graph problems by Robert Tarjan's 1972 paper Depth-First Search and Linear Graph Algorithms.

Core Principle

Explores each branch to full depth before backtracking, in contrast with breadth first search; the underlying strategy was investigated in the nineteenth century by French mathematician Charles Pierre Tremaux as a maze solving method, predating its formalization in computer science. 1

Cross-Tradition Connections