Depth-first search
Algorithm exploring branches fully before backtracking.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. It starts at a root node and explores as far as possible along each branch before backtracking, using extra memory, usually a stack, to keep track of discovered nodes. A version of DFS was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.
- field
- Computer science
- known_for
- Algorithm for traversing or searching tree or graph data structures
- time_complexity
- O(|V|+|E|) for traversing an entire graph
- space_complexity
- O(|V|) in worst case for storing stack and visited set
- originator
- Charles Pierre Trémaux (19th century)
Lore & Background
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. 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.
Reader's Guide
Depth-first search is significant as a fundamental algorithm in computer science for traversing or searching tree and graph data structures. Its time complexity is linear in the size of the graph, O(|V|+|E|), and its space complexity is O(|V|) in the worst case, making it comparable to breadth-first search. The choice between DFS and BFS depends on the different properties of the vertex orderings they produce. For applications such as artificial intelligence or web-crawling, where graphs may be too large or infinite, DFS is often performed to a limited depth, with space complexity proportional to the depth limit, which is much smaller than BFS. Iterative deepening depth-first search applies DFS repeatedly with increasing limits when the appropriate depth limit is not known a priori. DFS also lends itself well to heuristic methods for choosing likely-looking branches. The algorithm produces a Trémaux tree of traversed edges, and its vertex orderings—preordering, postordering, reverse preordering, and reverse postordering—have applications such as topological sorting of directed acyclic graphs.
Did You Know?
- 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.
- The edges traversed in a depth-first search form a Trémaux tree, a structure with important applications in graph theory.
- Reverse postordering produced by DFS yields a topological sorting of any directed acyclic graph.
- The non-recursive implementation of DFS uses a stack instead of a queue and delays checking whether a vertex has been discovered until it is popped from the stack.
Frequently Asked Questions
Who is Depth-first search?
DFS is a traversal algorithm in computer science that walks through tree or graph structures by committing fully to one path before retreating to try alternatives. Its roots stretch back to 19th-century France, where Charles Pierre Trémaux first explored the idea as a maze-solving technique.
What are Depth-first search's powers/role?
Its signature move is plunging as deep as possible down a single branch before backtracking, relying on a stack to remember discovered nodes. This lets it sweep an entire graph in O(|V|+|E|) time while keeping worst-case memory at O(|V|) for the stack and visited set.
How does Depth-first search's story end?
DFS wraps up its run the moment every reachable node has been visited and the pending-branch stack is fully drained. At that point it has either located the target it was hunting or confirmed the target simply isn't present in the reachable portion of the graph.
Why is Depth-first search important?
It offers a straightforward, low-memory way to explore connected components, detect cycles, and carry out topological sorting. Because of that versatility, it serves as a foundational building block for many more advanced graph algorithms in computer science.
Where did Depth-first search come from?
The concept traces back to 19th-century France, where mathematician Charles Pierre Trémaux studied it as a practical strategy for navigating mazes. It was later formalized into the general-purpose graph-traversal algorithm that modern computer science relies on.
More in Algorithms And Data Structures 1-24
Elsewhere in the Algorithms And Data Structures universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record