如何通过非递归的迭代式深度优先搜索（DFS）获取无向图中源点到终点的所有路径？

Yes, you absolutely can implement an iterative Depth-First Search (DFS) to retrieve all valid paths between a source and destination in an undirected graph. The recursive approach is intuitive, but iterative DFS can achieve the same result by explicitly simulating the call stack and tracking path/visited state for each branch of the search.

Implementation Overview #

In iterative DFS, we use an explicit stack to replicate the implicit call stack of recursive DFS. Each stack entry needs to capture three key pieces of information:

• The current node being explored
• The path taken to reach this node
• A set of nodes visited in this path (to avoid cycles within the path, since undirected graphs have bidirectional edges that could loop back to previous nodes in the same path)

Below are two common implementation approaches:

Approach 1: Explicit State Copying #

This method creates copies of the current path and visited set for each new neighbor, ensuring each stack entry has its own independent state. It’s straightforward to understand and debug:

def find_all_paths_iterative(graph, source, dest):
    all_paths = []
    # Stack entries: (current_node, current_path, visited_nodes_in_path)
    stack = [(source, [source], set([source]))]
    
    while stack:
        current, path, visited = stack.pop()
        
        # Save the path if we've reached the destination
        if current == dest:
            all_paths.append(path.copy())
            continue
        
        # Explore all neighbors not yet in the current path
        for neighbor in graph[current]:
            if neighbor not in visited:
                # Create new state for the next search branch
                new_visited = visited.copy()
                new_visited.add(neighbor)
                new_path = path.copy()
                new_path.append(neighbor)
                stack.append((neighbor, new_path, new_visited))
    
    return all_paths

Approach 2: Backtracking (Memory-Optimized) #

Instead of copying state for each branch, this approach reuses the same path and visited set, modifying them as we push/pop nodes from the stack. It mirrors the backtracking behavior of recursive DFS and uses less memory:

def find_all_paths_iterative_backtracking(graph, source, dest):
    all_paths = []
    # Stack entries: (current_node, neighbor_iterator, current_path, visited_nodes)
    stack = [(source, iter(graph[source]), [source], set([source]))]
    
    while stack:
        current, neighbors, path, visited = stack[-1]
        
        try:
            neighbor = next(neighbors)
            if neighbor not in visited:
                # Move to the neighbor and update state
                visited.add(neighbor)
                path.append(neighbor)
                stack.append((neighbor, iter(graph[neighbor]), path, visited))
                
                # Record the path if we've reached the destination
                if neighbor == dest:
                    all_paths.append(path.copy())
                    # Backtrack immediately after saving the path
                    path.pop()
                    visited.remove(neighbor)
                    stack.pop()
        except StopIteration:
            # No more neighbors to explore: backtrack to previous node
            stack.pop()
            if path:
                path.pop()
                if current != source:
                    visited.remove(current)
    
    return all_paths

Recursive vs. Iterative: Which is Better? #

Recursive DFS is almost always simpler to implement and read for this problem. Here’s a quick comparison with the recursive version:

def find_all_paths_recursive(graph, source, dest, path=None, visited=None):
    # Initialize state for the first call
    if path is None:
        path = [source]
    if visited is None:
        visited = set([source])
    
    # Base case: return the path if we've reached the destination
    if source == dest:
        return [path.copy()]
    
    all_paths = []
    for neighbor in graph[source]:
        if neighbor not in visited:
            # Update state and recurse
            visited.add(neighbor)
            path.append(neighbor)
            all_paths.extend(find_all_paths_recursive(graph, neighbor, dest, path, visited))
            # Backtrack: undo state changes after recursion
            path.pop()
            visited.remove(neighbor)
    
    return all_paths

Why Recursive is Easier: #

• The call stack automatically manages path and visited state for each search branch, so you don’t have to manually handle stack entries.
• Backtracking is intuitive—you just undo state changes after the recursive call returns.
• The code is shorter and more closely matches the logical flow of exploring paths.

When to Use Iterative: #

• Deep graphs: Recursive DFS can hit language-specific recursion depth limits (e.g., Python’s default ~1000). Iterative DFS avoids stack overflow issues.
• Performance-critical scenarios: In some languages, recursive calls have overhead that iterative code can avoid (though this is rarely a concern for most path-finding use cases).
• Explicit control: If you need fine-grained control over the search process (e.g., modifying the stack order for custom traversal strategies).

内容的提问来源于stack exchange，提问作者Liu Bei