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. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Origin YearMaze-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 PrincipleExplores 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 Connections
Associated With
Source Wikipedia: Depth-First Search
In Field
Source Wikipedia: Depth-First Search
Sources
1. Wikipedia: Depth-First Search
Wikimedia FoundationOpening paragraph
explores as far as possible along each branch before backtracking
History note, Tremaux
A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.
Introduction
depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
- History section
- In Field: Algorithms and Complexity Theory
- Associated With: Stack, Opening paragraph, on stack-based traversal
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.