Eric Campbell 6 min read Engineering

DFS: Depth-First Search Algorithm

Depth-First Search is one of the two fundamental graph traversal algorithms every developer should know cold. Unlike its sibling BFS, which explores neighbors level by level, DFS commits fully to a...

Key Insights

  • DFS explores graph branches completely before backtracking, making it ideal for problems requiring exhaustive path exploration like cycle detection and topological sorting
  • Choose recursive DFS for cleaner code on small graphs, but switch to iterative with an explicit stack when dealing with deep graphs to avoid stack overflow
  • DFS uses O(V) space compared to BFS’s O(V) worst case, but DFS typically performs better on sparse graphs and problems requiring backtracking

Depth-First Search is one of the two fundamental graph traversal algorithms every developer should know cold. Unlike its sibling BFS, which explores neighbors level by level, DFS commits fully to a path before retreating. It dives deep into a graph’s structure, hitting dead ends and backtracking until it exhausts all possibilities.

This “go deep first” approach makes DFS the natural choice for problems where you need to explore complete paths: detecting cycles, finding connected components, solving mazes, and performing topological sorts. If you’ve ever solved a maze by following one path until you hit a wall, then backing up to try the next option, you’ve already internalized DFS.

The algorithm appears everywhere in production code. Compilers use it for dependency resolution. Version control systems use it for commit graph analysis. Game engines use it for AI pathfinding when optimal paths aren’t required. Understanding DFS deeply will make you better at recognizing when it’s the right tool.

How DFS Works: The Algorithm

DFS operates on a simple principle: from any node, pick an unvisited neighbor and explore it immediately. Keep going until you reach a node with no unvisited neighbors, then backtrack to the most recent node that still has unexplored options.

The algorithm maintains two key pieces of state: a set of visited nodes and a stack of nodes to process. The stack can be explicit (using a data structure) or implicit (using the call stack via recursion).

Here’s the process:

  1. Start at a source node, mark it visited, push it to the stack
  2. Pop a node from the stack
  3. For each unvisited neighbor, mark it visited and push it to the stack
  4. Repeat until the stack is empty

The traversal order depends on the order you process neighbors. For the graph A→B, A→C, B→D, starting from A, you might visit A, C, B, D or A, B, D, C depending on neighbor ordering.

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(f"Visiting: {node}")
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_recursive(graph, 'A')
# Output: Visiting: A, B, D, E, F, C

Recursive vs. Iterative Implementation

The recursive implementation is elegant and maps directly to how we think about DFS. Each function call represents exploring a node, and the call stack handles backtracking automatically. But elegance has costs.

Python’s default recursion limit is 1000 calls. A graph with 10,000 nodes in a single chain will crash your program. Java and JavaScript have similar limitations. When you’re processing large graphs—social networks, web crawlers, file systems—recursive DFS becomes dangerous.

The iterative approach uses an explicit stack, giving you control over memory and avoiding stack overflow:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if node in visited:
            continue
            
        visited.add(node)
        print(f"Visiting: {node}")
        
        # Add neighbors in reverse order to match recursive traversal order
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    
    return visited

function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (visited.has(node)) continue;
        
        visited.add(node);
        console.log(`Visiting: ${node}`);
        
        // Process neighbors in reverse for consistent ordering
        const neighbors = graph[node] || [];
        for (let i = neighbors.length - 1; i >= 0; i--) {
            if (!visited.has(neighbors[i])) {
                stack.push(neighbors[i]);
            }
        }
    }
    
    return visited;
}

Notice the reversed() call in Python and backward iteration in JavaScript. Without this, iterative DFS processes neighbors in opposite order from recursive DFS because stacks are LIFO. This matters when traversal order affects your results.

My recommendation: Use recursive DFS for trees and small graphs where the code clarity helps. Switch to iterative for production systems processing user-generated graphs of unknown size.

DFS on Trees vs. Graphs

Trees are a special case of graphs: connected, acyclic, with a clear parent-child relationship. This simplicity means tree DFS doesn’t need a visited set—you can’t revisit nodes because there are no cycles.

Tree DFS comes in three flavors, each processing the current node at a different time:

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(node, result=None):
    """Process node BEFORE children. Good for copying trees."""
    if result is None:
        result = []
    if node is None:
        return result
    
    result.append(node.val)      # Process first
    preorder(node.left, result)
    preorder(node.right, result)
    return result

def inorder(node, result=None):
    """Process node BETWEEN children. Gives sorted order for BSTs."""
    if result is None:
        result = []
    if node is None:
        return result
    
    inorder(node.left, result)
    result.append(node.val)      # Process in middle
    inorder(node.right, result)
    return result

def postorder(node, result=None):
    """Process node AFTER children. Good for deletion, calculating sizes."""
    if result is None:
        result = []
    if node is None:
        return result
    
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.val)      # Process last
    return result

# Build tree:      1
#                /   \
#               2     3
#              / \
#             4   5

root = TreeNode(1, 
    TreeNode(2, TreeNode(4), TreeNode(5)), 
    TreeNode(3))

print(preorder(root))   # [1, 2, 4, 5, 3]
print(inorder(root))    # [4, 2, 5, 1, 3]
print(postorder(root))  # [4, 5, 2, 3, 1]

General graphs require cycle detection. Without tracking visited nodes, DFS on a cyclic graph loops forever. The visited set adds O(V) space overhead but is non-negotiable for correctness.

Common Applications and Problems

DFS shines in four categories of problems:

Cycle Detection is critical for dependency management, deadlock detection, and validating DAGs. The key insight: in a directed graph, a cycle exists if you encounter a node that’s currently on your recursion stack (not just visited):

def has_cycle_directed(graph):
    visited = set()
    rec_stack = set()  # Nodes in current recursion path
    
    def dfs(node):
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                # Found a back edge - cycle exists
                return True
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    
    return False

# Test with cyclic graph: A -> B -> C -> A
cyclic_graph = {'A': ['B'], 'B': ['C'], 'C': ['A']}
print(has_cycle_directed(cyclic_graph))  # True

# Test with acyclic graph: A -> B -> C
acyclic_graph = {'A': ['B'], 'B': ['C'], 'C': []}
print(has_cycle_directed(acyclic_graph))  # False

Connected Components identification uses DFS to find all nodes reachable from a starting point, then repeats for unvisited nodes. Each DFS call discovers one component.

Topological Sorting leverages postorder DFS. Nodes are added to the result after all their dependencies are processed, then the result is reversed. This gives a valid ordering for task scheduling, build systems, and course prerequisites.

Maze Solving treats each cell as a node with edges to adjacent open cells. DFS explores one complete path before trying alternatives, naturally implementing the “follow the wall” strategy.

Time and Space Complexity Analysis

DFS visits each vertex once and examines each edge once. For a graph with V vertices and E edges, the time complexity is O(V + E). This is optimal—you can’t do better than looking at every node and edge at least once.

Space complexity is O(V) in the worst case. The visited set requires O(V) space. The stack (explicit or implicit) can grow to O(V) when the graph is a single long chain. In practice, the stack depth equals the longest path from the starting node, which is often much less than V for well-connected graphs.

BFS has identical time complexity O(V + E) but different space characteristics. BFS’s queue can grow to O(V) when processing a star graph (one node connected to all others), while DFS’s stack stays at O(1) for the same structure. Conversely, for a long chain, DFS uses O(V) stack space while BFS uses O(1) queue space.

When to Use DFS vs. BFS

Choose DFS when:

  • You need to explore all paths or find any path (not necessarily shortest)
  • The problem involves backtracking (puzzles, constraint satisfaction)
  • You’re detecting cycles or performing topological sorts
  • Memory is constrained and the graph is wide but shallow
  • You need to process nodes in pre/post order

Choose BFS when:

  • You need the shortest path in an unweighted graph
  • You’re exploring level by level (social network degrees of separation)
  • The graph is deep but narrow
  • You need to find the closest node satisfying some condition

The decision often comes down to problem structure. Cycle detection, connected components, and topological sorting are DFS territory. Shortest path and level-order traversal belong to BFS. When either works, I default to DFS for its simpler implementation and typically better cache locality.

Master both algorithms. They’re the foundation for more advanced graph techniques like Dijkstra’s algorithm, strongly connected components, and network flow. The patterns you learn here—tracking visited state, managing a frontier of nodes to explore, processing in a specific order—appear throughout computer science.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.