深入理解深度优先搜索（DFS）

DFS 的两种实现方式

在 Python 中，DFS 可以通过 递归 或 显式使用栈 来实现。下面我们分别介绍这两种方法。

1. 递归实现 DFS（推荐初学者使用）

递归是最直观的 DFS 实现方式，它天然地利用了函数调用栈来保存回溯路径。

def dfs_recursive(graph, node, visited):    """    递归实现深度优先搜索    :param graph: 用邻接表表示的图，例如 {0: [1, 2], 1: [0], 2: [0]}    :param node: 当前访问的节点    :param visited: 记录已访问节点的集合    """    if node not in visited:        print(f"访问节点: {node}")        visited.add(node)                # 遍历当前节点的所有邻居        for neighbor in graph.get(node, []):            dfs_recursive(graph, neighbor, visited)# 示例图（无向图）graph = {    0: [1, 2],    1: [0, 3, 4],    2: [0, 5],    3: [1],    4: [1],    5: [2]}visited_set = set()dfs_recursive(graph, 0, visited_set)

2. 使用栈实现 DFS（非递归）

如果你担心递归深度过大导致栈溢出，可以使用显式的栈结构（如 Python 的 list）来模拟递归过程。

def dfs_iterative(graph, start_node):    """    使用栈实现深度优先搜索    :param graph: 邻接表表示的图    :param start_node: 起始节点    """    visited = set()    stack = [start_node]  # 初始化栈        while stack:        node = stack.pop()  # 弹出栈顶元素                if node not in visited:            print(f"访问节点: {node}")            visited.add(node)                        # 将邻居节点压入栈（注意顺序会影响遍历路径）            for neighbor in reversed(graph.get(node, [])):                if neighbor not in visited:                    stack.append(neighbor)# 使用相同的图进行测试dfs_iterative(graph, 0)

DFS 的应用场景

• 检测图中是否存在环
• 求解迷宫问题
• 拓扑排序（有向无环图）
• 寻找连通分量

常见误区与注意事项

1. 避免重复访问：务必使用 visited 集合记录已访问节点，否则可能陷入无限循环。

2. 图的表示方式：本教程使用邻接表（字典+列表），这是 Python 中最常用的图表示方法。

3. 递归 vs 栈：递归代码简洁但受限于最大递归深度；栈实现更灵活，适合处理大规模图。

总结

通过本教程，你应该已经掌握了 Python深度优先搜索 的基本原理和两种实现方式。无论是面试还是实际项目开发，DFS 都是一个非常实用的 图遍历算法。建议你动手运行上面的代码，并尝试修改图结构，观察输出结果的变化。

记住，理解 递归实现DFS 是学习更复杂图算法（如强连通分量、欧拉路径等）的基础。继续练习，你会越来越熟练！