Skip to main content
Definition Website Computer and Technology

Depth-First Search

Subject: Computer and Technology noun /ˈdɛpθˌfɜːrst ˈsɜːrtʃ/ 1 definition

  1. Definition (noun)

    Entry #53 · Updated

    Depth-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.ts while marking modules on the active path as visiting and completed modules as visited. When exploring src/auth/session.ts encounters an import pointing back to src/api/client.ts while client.ts is still visiting, DFS immediately detects the cycle and reports the exact circular dependency chain.