图的遍历算法：深度优先搜索-编程实验室

图的深度优先搜索（DFS）详解

深度优先搜索（Depth-First Search，DFS）是一种典型的图遍历算法，核心思想是**“先走到底，再回头”**：从起始节点出发，沿着一条路径尽可能深地访问节点，直到无法继续（无未访问的邻接节点），再回溯到上一个节点，探索其他未访问的分支。

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、核心概念

节点状态：通常标记为「未访问」「访问中」「已访问」，避免重复访问和处理环。
遍历方式：
- 递归实现：利用函数调用栈天然的回溯特性，简洁直观。
- 非递归实现：手动维护栈结构模拟递归过程，适合处理深度过大的场景（避免栈溢出）。
适用场景：路径查找、拓扑排序、连通分量、环检测、迷宫求解等。

二、图的存储方式

DFS的实现依赖图的存储结构，常用两种：

邻接矩阵：二维数组graph[i][j]表示节点i和j是否有边（适合稠密图）。
邻接表：数组+链表/列表，graph[i]存储节点i的所有邻接节点（适合稀疏图，效率更高）。

本文以邻接表为例实现。

三、递归实现 DFS

1. 算法步骤

初始化节点访问状态（如布尔数组visited）。
从起始节点开始，标记为已访问，输出/处理节点。
遍历该节点的所有邻接节点：若未访问，则递归访问该邻接节点。
若图存在多个连通分量，需遍历所有节点，对未访问的节点重复上述步骤。

2. 代码实现（Python）

defdfs_recursive(graph,node,visited):""" 递归实现DFS :param graph: 邻接表表示的图（字典/列表） :param node: 当前访问的节点 :param visited: 记录节点是否被访问的集合/数组 """# 标记当前节点为已访问visited.add(node)print(node,end=" ")# 处理节点（如输出）# 遍历所有邻接节点forneighboringraph[node]:ifneighbornotinvisited:# 递归访问未访问的邻接节点dfs_recursive(graph,neighbor,visited)# 示例：无向图（邻接表）if__name__=="__main__":# 图的邻接表表示（节点为0-4）graph={0:[1,2],1:[0,3,4],2:[0],3:[1],4:[1]}visited=set()# 记录访问过的节点（适合非连续节点）print("DFS递归遍历结果：")dfs_recursive(graph,0,visited)# 从节点0开始遍历

3. 输出结果

DFS递归遍历结果： 0 1 3 4 2

四、非递归（迭代）实现 DFS

1. 算法步骤

初始化栈（存入起始节点）和访问状态。
循环：弹出栈顶节点，若未访问则标记并处理。
将该节点的所有未访问邻接节点压入栈（注意顺序：后压入的先访问，保证DFS顺序）。
重复直到栈为空。

2. 代码实现（Python）

defdfs_iterative(graph,start):""" 非递归实现DFS（栈） :param graph: 邻接表表示的图 :param start: 起始节点 :return: 遍历顺序列表 """visited=set()# 记录已访问节点stack=[start]# 初始化栈，存入起始节点result=[]whilestack:# 弹出栈顶节点node=stack.pop()ifnodenotinvisited:# 标记为已访问，加入结果visited.add(node)result.append(node)# 邻接节点逆序压入栈（保证遍历顺序与递归一致）# 因为栈是后进先出，逆序压入后，正序弹出forneighborinreversed(graph[node]):ifneighbornotinvisited:stack.append(neighbor)returnresult# 示例调用if__name__=="__main__":graph={0:[1,2],1:[0,3,4],2:[0],3:[1],4:[1]}print("\nDFS非递归遍历结果：")print(dfs_iterative(graph,0))

3. 输出结果

DFS非递归遍历结果： [0, 1, 3, 4, 2]

五、处理非连通图

若图包含多个连通分量（无向图），需遍历所有节点，对未访问的节点启动DFS：

defdfs_connected_components(graph):visited=set()components=[]# 存储每个连通分量的遍历结果fornodeingraph:ifnodenotinvisited:component=[]# 递归DFS收集当前连通分量defdfs(node):visited.add(node)component.append(node)forneighboringraph[node]:ifneighbornotinvisited:dfs(neighbor)dfs(node)components.append(component)returncomponents# 示例：非连通图if__name__=="__main__":# 包含两个连通分量：0-1-2 和 3-4graph={0:[1],1:[0,2],2:[1],3:[4],4:[3]}print("\n非连通图的连通分量：")print(dfs_connected_components(graph))

输出：

非连通图的连通分量： [[0, 1, 2], [3, 4]]

六、DFS 特性与复杂度

时间复杂度：
- 邻接表：O(V + E)（V为节点数，E为边数），每个节点和边仅访问一次。
- 邻接矩阵：O(V²)，需遍历每个节点的所有可能邻接节点。
空间复杂度：
- 递归：O(V)（递归栈深度，最坏情况为链式图，栈深度=V）。
- 非递归：O(V)（栈存储节点，最坏情况存入所有节点）。
特点：
- 不保证找到最短路径（需BFS）。
- 易实现，适合深度优先的场景（如迷宫、拓扑排序）。
- 递归实现可能因深度过大导致栈溢出（需改用非递归）。