Depth-First Search
Subject: Computer and Technology noun /ˈdɛpθˌfɜːrst ˈsɜːrtʃ/ 1 definition
- graph-algorithms
- search-algorithms
- tree-traversal
- computer-science
-
Definition (noun)
Entry #53 · UpdatedDepth-First Search (DFS) is a graph and tree traversal algorithm that starts at a source vertex and explores as far along each branch as possible before backtracking to visit remaining unvisited paths. Using either recursion on the call stack or an explicit Last-In, First-Out (LIFO) stack—alongside a visited set to avoid infinite loops in cyclic graphs—it visits every reachable vertex and edge in O(V + E) time on adjacency lists. Unlike Breadth-First Search (BFS), which expands level by level to find shortest paths in unweighted graphs, DFS prioritizes deep path exploration and is foundational for cycle detection, topological sorting, and backtracking search.
Common Forms
Recursive DFS: Uses function recursion and the runtime call stack to descend through adjacent vertices and backtrack automatically upon returning, yielding concise code at the risk of stack overflow on very deep graphs.
Iterative Stack-Based DFS: Maintains an explicit heap-allocated stack and visited set inside a loop, avoiding call-stack limits on graphs with deep paths while offering fine-grained control over traversal state.
Tree Traversal Orders (Pre-Order, In-Order, and Post-Order): Specializes DFS for trees by determining whether each node is processed before its subtrees (pre-order), between left and right children in binary trees (in-order), or after all descendants finish (post-order).
Iterative Deepening DFS (IDDFS): Executes depth-limited DFS repeatedly with an incrementing depth threshold, preserving DFS's low memory footprint while guaranteeing discovery of minimum-depth solutions in large search spaces.
Example
A build tool resolves compilation order across 400 internal modules by running DFS from
src/index.tswhile marking modules on the active path asvisitingand completed modules asvisited. When exploringsrc/auth/session.tsencounters an import pointing back tosrc/api/client.tswhileclient.tsis stillvisiting, DFS immediately detects the cycle and reports the exact circular dependency chain.