Depth-first search
Algorithm exploring branches fully before backtracking.
Depth-first search (DFS) is a computer science algorithm used to traverse or search through tree and graph data structures. It begins at a root node—or, for graphs, any arbitrarily chosen node—and pushes as far down a single branch as possible before turning back. To manage this process, it relies on extra memory, typically a stack, to remember the nodes along the current path, which aids in backtracking. The method has roots in the 19th century, when French mathematician Charles Pierre Trémaux explored a similar technique for solving mazes.
The algorithm’s performance varies by use case. In theoretical computer science, where DFS typically scans an entire graph, it runs in time proportional to the total number of vertices and edges, written as O(|V|+|E|). This is linear relative to the graph’s size. In such cases, it also uses O(|V|) space in the worst case to store the stack of vertices on the current search path and the set of visited nodes. These time and space bounds match those of breadth-first search, so the choice between the two often depends on the different vertex orderings they produce rather than on complexity.
For domain-specific applications like artificial intelligence or web crawling, the graph may be too large to fully explore or even infinite, risking non-termination. Here, search is limited to a fixed depth, and due to resource constraints, visited nodes are not tracked. Time remains linear in the number of expanded vertices and edges, though some nodes may be revisited or skipped. Space complexity, however, is only proportional to the depth limit—far smaller than breadth-first search for the same depth. DFS also works well with heuristic methods that pick promising branches. When the ideal depth limit is unknown, iterative deepening depth-first search runs DFS repeatedly with increasing limits. In AI analysis, if the branching factor exceeds one, iterative deepening only adds a constant factor to runtime because node counts grow geometrically per level.
DFS can also sample graph nodes, but incomplete DFS, like incomplete BFS, tends to favor nodes with high degrees.
Consider a graph with nodes A, B, C, D, E, F, G. Starting at A, choosing left edges before right, and remembering visited nodes, DFS visits: A, B, D, F, E, C, G. The edges used form a Trémaux tree, important in graph theory. Without remembering visited nodes, the search loops forever: A, B, D, F, E, A, B, D, F, E... never reaching C or G. Iterative deepening avoids this infinite loop and visits all nodes.
The output of a DFS can be described as a spanning tree of the reached vertices. Based on this tree, the original graph’s edges fall into three classes: forward edges (pointing from a node to a descendant), back edges (pointing to an ancestor), and cross edges (neither). Tree edges—those in the spanning tree—are sometimes separated from forward edges. In an undirected graph, all edges are either tree edges or back edges.
DFS can also order vertices linearly in four ways: preordering (first-visit order, as in the example above; for expression trees, this yields Polish notation); postordering (last-visit order; for expression trees, this yields reverse Polish notation); reverse preordering (the opposite of preordering, not the same as postordering); and reverse postordering (the opposite of postordering).
- 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 used to traverse or search tree and graph data structures. It begins at a chosen root node—or an arbitrary node in a graph—and proceeds along each branch as far as possible before retreating, a process known as backtracking. To manage this backtracking, the algorithm requires extra memory, typically a stack, to record the nodes discovered along the current path. A precursor to DFS was studied in the 19th century by French mathematician Charles Pierre Trémaux as a method for solving mazes.
The algorithm’s performance varies by application. When traversing an entire graph, DFS runs in time linear to the number of vertices and edges, and in the worst case uses space proportional to the number of vertices to store the stack and visited set. In domains like artificial intelligence or web crawling, the graph may be too large or infinite to explore fully. Here, search is limited to a fixed depth, using only space proportional to that depth limit, and DFS adapts well to heuristic branch selection. When the ideal depth is unknown, iterative deepening depth-first search repeatedly applies DFS with increasing depth limits, increasing runtime by only a constant factor due to geometric node growth. DFS can also sample graph nodes, though incomplete searches are biased toward high-degree nodes.
The search produces a spanning tree of visited vertices. Edges of the original graph are classified as forward, back, or cross edges; in undirected graphs, only tree and back edges exist. DFS can linearly order vertices in several ways: preordering (first-visit order), postordering (last-visit order), and their reverses. For binary trees, in-ordering and reverse in-ordering are also possible.
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
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