Depth-First Search (DFS)

Definition: A graph traversal algorithm that explores as deep as possible along each branch before backtracking to explore the next unvisited branch.

How It Works

DFS uses a Stack (LIFO), either explicitly or implicitly via recursion (the call stack is a stack); the two forms are behaviorally equivalent:

def dfs(node, visited):
    visited.add(node)
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs(neighbor, visited)   # descend before trying siblings

The visited set prevents infinite loops on cyclic graphs. Because DFS commits to one branch and follows it all the way down before backing out, it produces three classifications useful for further analysis:

Discovery time / finish time: when a node is first visited, and when the recursive call for it fully completes (all descendants processed).
Edge types: tree edges (part of the DFS tree), back edges (pointing to an ancestor still on the active recursion stack), forward edges, and cross edges. Back edges specifically indicate a cycle in the graph.

Iterative-deepening DFS (IDDFS) combines DFS’s low memory footprint with BFS’s shortest-path guarantee: it re-runs depth-limited DFS with an increasing depth cutoff (1, then 2, then 3, …) until the target is found. This is useful when the graph or tree is too large to hold a full BFS frontier in memory, at the cost of revisiting shallow nodes multiple times.

Complexity Analysis

Metric	Complexity
Time	O(V + E)
Space (recursive)	O(V) worst case, one stack frame per node on a long chain
Space (iterative, explicit stack)	O(V) worst case, same bound without call-stack limits

V is vertices, E is edges; every vertex is visited once and every edge is examined once across the full traversal.

Why It Matters

Ideal for topological sorting (via post-order finish times), cycle detection (via back-edge detection), connected-component labeling, and solving mazes or puzzles via backtracking.
Uses far less memory than Breadth-First Search (BFS) on graphs with a huge branching factor but modest depth, since it only ever needs to hold one root-to-leaf path on the stack, versus BFS potentially holding an entire wide frontier.
Underlies compiler dependency resolution (topological sort of a build graph) and tools like git’s reachability analysis for garbage-collecting unreachable commits, since both are fundamentally “walk this DAG and process nodes only after their dependencies” problems.

Common Pitfalls

Does NOT guarantee the shortest path in unweighted graphs; it can return a much longer path than Breadth-First Search (BFS) would, since it commits to whichever branch it explores first regardless of distance.
Can cause a stack overflow on very deep graphs if implemented recursively, e.g. a linked-list-shaped graph with 100,000 nodes exceeds most default call stack limits; an explicit iterative stack avoids this by living on the heap instead of the call stack.
Failing to distinguish “currently on the recursion stack” (still being explored) from “fully visited” (finished) breaks cycle detection in directed graphs; a node that’s been popped and finished is not the same state as a node still actively being explored higher up the stack.
Traversing an undirected graph and treating the edge back to the immediate parent as a false cycle, unless that specific parent edge is explicitly excluded from the back-edge check.
Reusing a single global visited set across multiple independent DFS calls (e.g. one per connected component) without resetting it, silently skipping components that should be explored separately.

Comparison

	DFS	BFS	Topological Sort (Kahn’s)
Traversal order	Deep first, then backtrack	Level by level	Zero-in-degree order
Data structure	Stack / recursion	Queue	Queue of zero-in-degree nodes
Shortest path guarantee	No	Yes, unweighted only	N/A (ordering, not shortest path)
Memory profile	One root-to-leaf path	Full frontier layer	Frontier of ready nodes
Natural use case	Cycle detection, backtracking	Shortest hops	Build/dependency ordering

Example

Detecting cycles in a dependency graph during build system execution is a classic DFS application:

visit(A): mark A as "in progress"
  visit(B): mark B as "in progress"
    visit(C): mark C as "in progress"
      visit(A): A is already "in progress" -> CYCLE DETECTED

On the graph A -> B -> C -> A, DFS descends A -> B -> C, then finds C’s only outgoing edge points back to A, which is still on the active recursion stack (marked “in progress,” not yet “finished”). That’s what signals a genuine cycle rather than simply revisiting a node through a completed, unrelated path.

Discovery/Finish Times, Traced

Running DFS on the graph A -> B, A -> C, B -> D, C -> D from A, with a global clock incrementing on every discovery and finish:

visit A: discovery[A]=1
  visit B: discovery[B]=2
    visit D: discovery[D]=3
    D has no unvisited neighbors: finish[D]=4
  B has no more unvisited neighbors: finish[B]=5
  visit C: discovery[C]=6
    C's neighbor D already visited (and finished) -> cross edge, not a back edge, no cycle
  C has no more unvisited neighbors: finish[C]=7
A has no more unvisited neighbors: finish[A]=8

Sorting nodes by decreasing finish time (A=8, C=7, B=5, D=4) gives A, C, B, D, a valid topological order: every directed edge in the graph goes from a node with a later finish time to one with an earlier finish time, which is exactly the invariant that makes the decreasing-finish-time ordering a correct topological sort.

Variants

Iterative DFS with an explicit stack: avoids recursion depth limits entirely by pushing/popping nodes from a heap-allocated stack instead of the call stack, at the cost of slightly more verbose code to manage the “unvisited neighbor” state manually.
```
stack=[A]  visited={A}
pop A: push unvisited neighbors B, C -> stack=[B,C]  visited={A,B,C}
pop C: push unvisited neighbor D -> stack=[B,D]       visited={A,B,C,D}
pop D: no unvisited neighbors -> stack=[B]
pop B: no unvisited neighbors -> stack=[]  done
```
Note the traversal order here (A, C, D, B) can differ from the recursive version depending on the order neighbors are pushed, since a stack reverses whatever order they’re added in.
DFS for topological sort: run DFS to completion, recording each node’s finish time, then reverse the finish-order to get a valid topological ordering. This works because a node only finishes after all of its dependencies (descendants in the DFS tree) have finished first.
Backtracking: a direct application of DFS where, after fully exploring a branch, the algorithm undoes (“backtracks”) any state changes made along that branch before trying the next one. This is the basis for solving Sudoku, N-Queens, and combinatorial search problems.

FAQ

Is DFS always recursive? No. Recursion is the natural expression since the call stack behaves exactly like an explicit stack, but any DFS can be rewritten iteratively with a manually managed stack, which is often necessary to avoid stack-depth limits on deep graphs.

Does DFS visit every node? Only every node reachable from the starting node. To visit an entire graph with multiple disconnected components, DFS must be re-launched from any still-unvisited node after the first call returns.

Real-World Systems

git’s garbage collector uses a DFS-style reachability walk from all refs (branches, tags, HEAD) to determine which commits and objects are still reachable; anything not visited is eligible for pruning.
Build systems and package managers (Make, npm, Cargo) perform a DFS-based topological sort over the dependency graph to decide build or install order, ensuring every dependency is built before whatever depends on it.
Compilers use DFS for control-flow graph analysis, detecting unreachable code and analyzing loop structure by classifying edges the same way (tree, back, forward, cross) described above.
Maze-generation and maze-solving algorithms commonly use randomized DFS, carving passages by recursively visiting unvisited cells and backtracking at dead ends.

Referenced by

Dig deeper

Spot an error in this note?