第39课 - 深度优先搜索（DFS）

所属模块：图算法难度：Intermediate 标签：dfs, stack, recursive, visited 上一课：图的表示 下一课：广度优先搜索（BFS）

1. 学习目标

理解深度优先搜索（DFS）的核心思想与工作原理。
掌握使用递归和显式栈两种方式实现DFS算法。
应用DFS来解决图的连通性检查问题。
识别并处理DFS中可能出现的环路问题。

2. 核心概念

什么是DFS？

想象你正在一个迷宫里寻宝。你会选择一条路一直走下去，直到碰壁（死胡同）才返回上一个分岔口，尝试另一条路。这种“一条路走到黑”的策略，就是深度优先搜索。

在图中，DFS从一个起始节点开始，尽可能深地探索图的分支。当节点v的所有邻接点都已被访问过，搜索将回溯到发现v的节点，继续探索其他未访问的分支。

关键要素

栈（Stack）：无论是递归调用栈还是手动维护的栈，DFS的“后进先出”特性完美契合了回溯的逻辑。
已访问标记（Visited）：一个集合或布尔数组，用来记录哪些节点已经被访问过，防止在图中成环时陷入死循环。
图：需要遍历的数据结构，通常使用邻接表或邻接矩阵表示（参考上一课）。

算法流程

选择一个起始节点，将其标记为已访问，并压入栈中（或开始递归）。
从栈顶取出一个节点。
遍历该节点的所有邻接节点：
- 如果邻接节点未被访问，则将其标记为已访问，压入栈中，并立即开始对该节点的探索（递归或循环）。
- 如果邻接节点已被访问，则跳过。
重复步骤2-3，直到栈为空（表示所有可达节点都已探索完毕）。

3. 代码示例

我们将使用邻接表来表示图，并分别用递归和栈两种方式实现DFS。

from collections import defaultdict

# 首先，定义一个图（使用邻接表）
class Graph:
    def __init__(self):
        self.graph = defaultdict(list) # 字典的默认值是空列表
    
    def add_edge(self, u, v):
        """添加一条从u到v的边（无向图）"""
        self.graph[u].append(v)
        self.graph[v].append(u) # 无向图，双向添加

    def dfs_recursive(self, start, visited=None):
        """方法一：递归实现DFS"""
        if visited is None:
            visited = set() # 初始化已访问集合
        
        # 访问当前节点
        print(start, end=' ')
        visited.add(start)
        
        # 递归访问所有未访问的邻接节点
        for neighbor in self.graph[start]:
            if neighbor not in visited:
                self.dfs_recursive(neighbor, visited)
    
    def dfs_stack(self, start):
        """方法二：使用显式栈实现DFS"""
        visited = set()
        stack = [start] # 初始化栈
        
        while stack:
            node = stack.pop() # 从栈顶取出节点
            
            if node not in visited:
                # 访问节点
                print(node, end=' ')
                visited.add(node)
                
                # 将所有未访问的邻接节点逆序压栈
                # 逆序是为了让第一个邻接点先被访问，与递归顺序保持一致（非必需）
                for neighbor in reversed(self.graph[node]):
                    if neighbor not in visited:
                        stack.append(neighbor)

# 创建示例图
g = Graph()
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (3, 4), (3, 5), (4, 5)]
for u, v in edges:
    g.add_edge(u, v)

print("图的结构（邻接表）:")
for node in g.graph:
    print(f"{node} -> {g.graph[node]}")

print("\n递归DFS遍历结果（从节点0开始）:")
g.dfs_recursive(0)
print("\n\n栈实现的DFS遍历结果（从节点0开始）:")
g.dfs_stack(0)

运行输出：

图的结构（邻接表）:
0 -> [1, 2]
1 -> [0, 3, 4]
2 -> [0, 4]
3 -> [1, 4, 5]
4 -> [1, 2, 3, 5]
5 -> [3, 4]

递归DFS遍历结果（从节点0开始）:
0 1 3 4 2 5 

栈实现的DFS遍历结果（从节点0开始）:
0 1 3 4 5 2

（注：由于邻接表中邻居节点的存储顺序和压栈顺序不同，两种实现的遍历顺序可能略有差异，但都深度优先地访问了所有节点。）

4. 实践练习

练习1：基础遍历

给定一个图的邻接表，编写一个函数 dfs_traversal(graph, start_node)，返回从 start_node 开始DFS遍历的节点顺序列表。

# 测试图
test_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
# 预期输出 (顺序可能略有不同): ['A', 'B', 'D', 'E', 'F', 'C']

练习2：连通分量计数

一个图可能不是完全连通的，它由多个连通分量组成。编写一个函数 count_connected_components(graph)，使用DFS来计算图的连通分量数量。

# 测试图（有两个连通分量：{A, B, C} 和 {D, E}）
disconnected_graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B'],
    'D': ['E'],
    'E': ['D']
}
# 预期输出: 2

练习3：路径寻找（进阶）

编写一个函数 dfs_path_exists(graph, start, end)，使用DFS判断图中是否存在从节点 start 到节点 end 的路径。如果存在，返回 True；否则返回 False。

# 使用练习2中的图
# 测试1: dfs_path_exists(test_graph, 'A', 'F') -> True
# 测试2: dfs_path_exists(disconnected_graph, 'A', 'D') -> False

5. 常见错误

忘记标记已访问节点：这是最致命的错误。对于含有环的图，如果不及时将访问过的节点放入visited集合，算法会在环中无限循环。
```
# 错误示例（会导致无限循环）
for neighbor in self.graph[node]:
    # if neighbor not in visited: # 这个检查是必须的！
    stack.append(neighbor)
```
递归深度过大导致栈溢出：对于非常大的图或呈长链状的图，递归版本的DFS可能耗尽系统的调用栈。此时应改用显式栈的迭代版本。
混淆DFS与BFS的遍历顺序：记住，DFS是“一钻到底”，BFS（下一课）是“层层推进”。如果题目要求特定的顺序，选错算法会导致结果错误。
图的表示有误：在构建无向图时，忘记添加双向边（u->v 和 v->u），会导致遍历不完整。

6. 小结

深度优先搜索（DFS） 是一种用于遍历或搜索图/树的算法，其核心策略是尽可能深地探索分支，直到无法继续再回溯。
关键工具：栈（系统递归栈或手动维护的栈）和 visited集合。
两种实现：
1. 递归：代码简洁，但对栈深度有限制。
2. 迭代（使用栈）：更灵活，不受系统栈深度限制。
核心应用：连通性检查、路径寻找、拓扑排序（后续课程）、检测环等。
一定要维护一个visited集合，这是保证算法能在图中正确终止的前提。

掌握DFS是学习更复杂图算法（如拓扑排序、强连通分量）的重要基础。下一课，我们将学习另一种重要的图遍历算法——广度优先搜索（BFS）。

练习编辑器

rust