Depth-First Search - Going Deep Before Wide

Depth-First Search (DFS) is a graph and tree traversal algorithm that commits fully to one direction — going as deep as possible along each branch before backtracking and trying another. Where BFS explores level by level, DFS dives straight to the bottom of each path first.

A Brief History

DFS has ancient roots. Charles Pierre Trémaux, a 19th-century French mathematician, described a maze-solving strategy in the 1880s that is essentially DFS — mark your path, go as far as you can, and backtrack when stuck. The algorithm was formalized for computers by Claude Shannon and others in the 1950s while working on maze-solving robots. Robert Tarjan significantly advanced DFS theory in 1972 with his landmark paper on graph connectivity, giving us Tarjan’s algorithm for finding strongly connected components in a single DFS pass.

How It Works

DFS uses a stack — either explicitly or via the call stack through recursion:

Start: Push the starting node onto the stack and mark it as visited.
Pop: Take the top node from the stack.
Process: Work with the current node (check if it’s the target, collect data, etc.).
Push neighbors: For each unvisited neighbor, mark it visited and push it onto the stack.
Repeat: Continue until the stack is empty or the target is found.

The recursive version is often cleaner: process the current node, then recursively call DFS on each unvisited neighbor. The call stack implicitly acts as the DFS stack.

The key property: DFS follows one path all the way to its end before trying any alternative. This makes it naturally suited for problems about paths, cycles, and ordering.

Time Complexity

Like BFS, DFS visits every vertex and traverses every edge exactly once:

Case	Complexity
All cases	$O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges. The traversal is linear in the size of the graph.

Space Complexity

DFS uses $O(h)$ space where $h$ is the maximum depth of the recursion (or the height of the tree). In the worst case (a linear chain of nodes), this is $O(V)$ — the entire graph in memory. For balanced binary trees, it’s $O(\log n)$ — just the height.

This makes DFS significantly more memory-efficient than BFS for deep, narrow graphs. A balanced tree with one million nodes needs only 20 stack frames for DFS, versus potentially 500,000 queue entries for BFS.

Warning: Recursive DFS on very large graphs can cause a stack overflow. JavaScript’s default call stack is limited (typically 10,000–15,000 frames). Use an iterative version with an explicit stack for production code on large inputs.

Advantages and Disadvantages

Advantages:

Memory efficient for deep graphs — uses $O(h)$ space vs BFS’s $O(V)$
Naturally finds paths through mazes and trees
Essential for topological sorting, cycle detection, and SCC detection
Recursive implementation is often elegant and readable
Discovers far-reaching structure (cycles, connectivity) more naturally than BFS

Disadvantages:

Does not guarantee the shortest path — it finds a path, not the shortest one
Recursive implementation risks stack overflow on large inputs
Can get “lost” in infinite graphs without proper visited tracking
Less intuitive than BFS for level-ordered problems

When to Use DFS

DFS is the right tool when:

Cycle detection — DFS naturally detects back-edges, which indicate cycles in a directed graph
Topological sorting — ordering nodes such that all edges point forward (used for task scheduling, dependency resolution)
Maze solving — exploring paths until you find the exit (or a dead end), then backtracking
Finding connected components — run DFS from each unvisited node to discover all components
Strongly connected components — Tarjan’s and Kosaraju’s algorithms are both DFS-based
Tree traversals — pre-order, in-order, and post-order traversals are all DFS variants
Game AI — exploring all possible moves in a game tree (often combined with alpha-beta pruning)

For shortest path problems, use Breadth-First Search (unweighted) or Dijkstra’s algorithm (weighted). DFS finds paths, not optimal ones.

In conclusion, DFS is one of the most versatile algorithms in computer science. Its stack-based exploration unlocks a surprising range of applications — from topological ordering to cycle detection to connected components. Master DFS and you hold the key to a large fraction of graph algorithm problems.