Implementing DFS: Recursive vs Iterative Methods

You want to learn about DFS—one of the most fundamental graph traversal algorithms that explores as far as possible along each branch before backtracking, right? DFS is widely used in pathfinding, topological sorting, connected component detection, and solving puzzles (like mazes). It can be implemented iteratively (with a stack) or recursively (using the call stack), and works for both directed and undirected graphs.

I. Core Principles of DFS

DFS follows a “go deep first, backtrack later” strategy. Imagine exploring a maze: you follow one path until you hit a dead end, then backtrack to the last 岔路口 and try the next path. Here’s the step-by-step workflow:

Start with a Node: Select an initial node (start node) and mark it as visited.
Explore a Neighbor: Choose an unvisited neighbor of the current node, mark it as visited, and repeat this step (go deeper).
Backtrack: When the current node has no unvisited neighbors, backtrack to the previous node and repeat step 2.
Terminate: Stop when all reachable nodes from the start node have been visited.

Key Concepts

Visited Tracking: Critical to avoid revisiting nodes (and infinite loops). Typically implemented with a boolean array, set, or hash map.
Backtracking: The process of returning to a previous node after exploring all its neighbors—DFS’s defining feature.
Traversal Order: DFS has three common traversal orders for trees (a special case of graphs):
- Pre-order: Visit current node → traverse left subtree → traverse right subtree.
- In-order: Traverse left subtree → visit current node → traverse right subtree.
- Post-order: Traverse left subtree → traverse right subtree → visit current node.

II. Complete Implementation Code (Python)

Below are DFS implementations for graphs (adjacency list representation) and binary trees (the most common DFS use case), including both recursive and iterative approaches:

1. DFS for Graphs (Adjacency List)

Graphs can be directed or undirected. We’ll use an adjacency list (dictionary) to represent the graph.

python

运行

def dfs_graph_recursive(graph, start, visited=None):
    """
    Recursive DFS for graphs (adjacency list)
    :param graph: Dictionary representing the graph (key: node, value: list of neighbors)
    :param start: Starting node for traversal
    :param visited: Set of visited nodes (avoids cycles)
    :return: List of nodes in DFS traversal order
    """
    # Initialize visited set if not provided
    if visited is None:
        visited = set()
    
    # Mark current node as visited and add to traversal result
    visited.add(start)
    traversal = [start]
    
    # Recursively visit all unvisited neighbors
    for neighbor in graph[start]:
        if neighbor not in visited:
            # Extend traversal with results from neighbor's DFS
            traversal.extend(dfs_graph_recursive(graph, neighbor, visited))
    
    return traversal

def dfs_graph_iterative(graph, start):
    """
    Iterative DFS for graphs (adjacency list) using a stack
    :param graph: Dictionary representing the graph
    :param start: Starting node
    :return: List of nodes in DFS traversal order
    """
    visited = set()
    stack = [start]  # Stack stores nodes to visit
    traversal = []
    
    while stack:
        # Pop the top node from the stack (LIFO: Last-In-First-Out)
        current = stack.pop()
        
        if current not in visited:
            # Mark as visited and add to traversal
            visited.add(current)
            traversal.append(current)
            
            # Push unvisited neighbors to the stack (reverse order to maintain traversal order)
            # Reverse ensures neighbors are processed in the same order as recursive DFS
            for neighbor in reversed(graph[current]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal

# Test Graph (Undirected)
if __name__ == "__main__":
    # Adjacency list: node -> list of neighbors
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }

    print("Graph DFS (Recursive):", dfs_graph_recursive(graph, 'A'))
    # Output (example): ['A', 'B', 'D', 'E', 'F', 'C'] (order may vary based on neighbor order)
    
    print("Graph DFS (Iterative):", dfs_graph_iterative(graph, 'A'))
    # Output (example): ['A', 'C', 'F', 'E', 'B', 'D'] (reverse neighbor order → same as recursive if reversed)

2. DFS for Binary Trees (Pre-order, In-order, Post-order)

Binary trees are hierarchical graphs with at most two children per node (left and right). DFS traversal orders are well-defined here.

python

运行

# Define a Binary Tree Node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Recursive DFS Traversals for Binary Trees
def pre_order_recursive(node, traversal=None):
    """Pre-order: Visit → Left → Right"""
    if traversal is None:
        traversal = []
    if node:
        traversal.append(node.val)
        pre_order_recursive(node.left, traversal)
        pre_order_recursive(node.right, traversal)
    return traversal

def in_order_recursive(node, traversal=None):
    """In-order: Left → Visit → Right (yields sorted order for BST)"""
    if traversal is None:
        traversal = []
    if node:
        in_order_recursive(node.left, traversal)
        traversal.append(node.val)
        in_order_recursive(node.right, traversal)
    return traversal

def post_order_recursive(node, traversal=None):
    """Post-order: Left → Right → Visit"""
    if traversal is None:
        traversal = []
    if node:
        post_order_recursive(node.left, traversal)
        post_order_recursive(node.right, traversal)
        traversal.append(node.val)
    return traversal

# Iterative Pre-order DFS (Stack-based)
def pre_order_iterative(root):
    traversal = []
    stack = []
    current = root
    
    while current or stack:
        # Traverse to the leftmost node, visiting each node
        while current:
            traversal.append(current.val)
            stack.append(current)
            current = current.left
        
        # Backtrack: pop from stack and move to right child
        current = stack.pop()
        current = current.right
    
    return traversal

# Test Binary Tree
if __name__ == "__main__":
    # Build a sample binary tree:
    #        1
    #         \
    #          2
    #         /
    #        3
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)

    print("\nBinary Tree Pre-order (Recursive):", pre_order_recursive(root))  # Output: [1, 2, 3]
    print("Binary Tree Pre-order (Iterative):", pre_order_iterative(root))    # Output: [1, 2, 3]
    print("Binary Tree In-order (Recursive):", in_order_recursive(root))      # Output: [1, 3, 2]
    print("Binary Tree Post-order (Recursive):", post_order_recursive(root))  # Output: [3, 2, 1]

III. Key Code Explanations

1. Graph DFS

Recursive Approach: Uses the call stack to handle backtracking. The visited set is passed by reference to avoid reinitializing it for each recursive call.
Iterative Approach: Uses an explicit stack to simulate the call stack. We pop() the top node (LIFO order) and push its unvisited neighbors (in reverse order to match recursive traversal order).
Cycle Prevention: The visited set ensures we don’t revisit nodes (critical for cyclic graphs, e.g., a graph with edges A→B and B→A).

2. Binary Tree DFS

Pre-order: Visits the current node first, then explores left and right children. Useful for creating a copy of the tree or prefix traversal.
In-order: Explores left children first, then visits the current node. For Binary Search Trees (BSTs), this yields nodes in sorted order (a key use case).
Post-order: Explores left and right children first, then visits the current node. Useful for deleting the tree or postfix traversal.

IV. Algorithm Performance Analysis

Metric	Result	Explanation
Time Complexity	O(V + E)	– `V`: Number of vertices (nodes).- `E`: Number of edges.Each node is visited once (O(V)), and each edge is checked once (O(E)).
Space Complexity	O(V)	– Recursive: O(V) for the call stack (worst case: skewed graph/tree).- Iterative: O(V) for the stack (worst case: all nodes pushed to stack).
Use Cases	Pathfinding (e.g., maze solving), connected components, topological sorting, cycle detection, BST in-order traversal (sorted order).

Worst-Case Space Scenario

A skewed graph/tree (e.g., a linked list: A→B→C→D→E) requires O(V) space for the stack/call stack (all nodes are in the stack at once).
A balanced tree (e.g., a binary tree with log V depth) requires O(log V) space (only the current path is in the stack).

V. DFS vs. BFS (Breadth-First Search)

Feature	DFS	BFS
Traversal Strategy	Depth-first (go deep, then backtrack)	Breadth-first (explore all neighbors at current depth first)
Data Structure	Stack (recursive: call stack)	Queue
Space Complexity	O(V) (worst case)	O(V) (worst case: complete graph)
Path Finding	Finds a path, but not necessarily the shortest	Finds the shortest path in unweighted graphs
Use Cases	Maze solving, topological sorting, cycle detection, BST sorting	Shortest path (unweighted), level-order traversal, neighbor discovery (e.g., social networks)
Implementation	Easier to code recursively	Easier to code iteratively (queue)

VI. Practical Applications of DFS

Pathfinding and Maze Solving: DFS explores all possible paths in a maze until it finds an exit (e.g., solving a Sudoku puzzle by trying all possible numbers and backtracking).
Topological Sorting: Critical for dependency graphs (e.g., course prerequisites, task scheduling). DFS processes nodes and adds them to a stack in post-order, then reverses the stack for the topological order.
Cycle Detection: Detects cycles in graphs (e.g., detecting deadlocks in operating systems, circular dependencies in projects).
Connected Components: Finds all nodes reachable from a start node (e.g., identifying clusters in a social network, connected regions in an image).
Binary Search Tree (BST) Operations: In-order DFS traversal of a BST returns nodes in sorted order (used for searching, sorting, and range queries).