别再死记硬背DFS/BFS了！用Python+邻接矩阵手把手带你跑一遍遍历过程

别再死记硬背DFS/BFS了用Python邻接矩阵手把手带你跑一遍遍历过程算法学习最怕的就是死记硬背尤其是像深度优先搜索(DFS)和广度优先搜索(BFS)这样的基础图算法。很多初学者对着书本上的伪代码和理论描述一头雾水考试时只能机械地套用模板一旦遇到变种题目就束手无策。今天我们就用Python和邻接矩阵带你真正理解这两种遍历算法的精髓。邻接矩阵是图论中最基础的表示方法之一它用二维数组清晰地展现了图中顶点之间的连接关系。我们将从零开始构建邻接矩阵然后通过打印中间状态的方式一步步观察DFS和BFS是如何走完整个图的。这种方法不仅能帮你理解算法原理更能培养解决实际图问题的思维能力。1. 邻接矩阵图的数学表达在开始遍历之前我们需要先理解邻接矩阵这个基础数据结构。假设我们有一个无向图包含7个顶点(0-6)其连接关系如下0 - 1 - 3 - 4 - 2 \ \ / 2 6 5用邻接矩阵表示这个图就是一个7×7的二维数组其中matrix[i][j]1表示顶点i和j之间有边相连0则表示没有连接。在Python中我们可以用NumPy数组来表示import numpy as np adj_matrix np.array([ [0, 1, 1, 0, 0, 0, 1], # 顶点0的连接情况 [1, 0, 0, 1, 0, 0, 1], # 顶点1 [1, 0, 0, 0, 1, 0, 0], # 顶点2 [0, 1, 0, 0, 1, 0, 0], # 顶点3 [0, 0, 1, 1, 0, 1, 0], # 顶点4 [0, 0, 0, 0, 1, 0, 0], # 顶点5 [1, 1, 0, 0, 0, 0, 0] # 顶点6 ])注意无向图的邻接矩阵是对称的因为如果顶点i与j相连那么j也一定与i相连。为了更直观地理解这个矩阵我们可以将其可视化0 1 2 3 4 5 6 0 [0 1 1 0 0 0 1] 1 [1 0 0 1 0 0 1] 2 [1 0 0 0 1 0 0] 3 [0 1 0 0 1 0 0] 4 [0 0 1 1 0 1 0] 5 [0 0 0 0 1 0 0] 6 [1 1 0 0 0 0 0]这个矩阵就是我们后续进行DFS和BFS遍历的基础。理解了这个数据结构算法的实现就会变得清晰很多。2. 深度优先搜索(DFS)探索图的纵深深度优先搜索就像走迷宫时采用的策略选择一条路走到底直到走不通再回溯。这种不撞南墙不回头的方式非常适合发现图中的连通分量和路径问题。2.1 DFS的核心思想DFS算法遵循以下几个基本原则从起始顶点开始标记为已访问递归访问所有未访问的相邻顶点当没有未访问的相邻顶点时回溯到上一个顶点用Python实现DFS时我们需要维护两个关键数据结构visited集合记录已经访问过的顶点递归调用栈隐式地保存了当前的搜索路径2.2 一步步实现DFS遍历让我们从顶点0出发看看DFS如何遍历这个图。以下是完整的Python实现def dfs(adj_matrix, start): n len(adj_matrix) visited set() traversal_order [] def _dfs(node): visited.add(node) traversal_order.append(node) print(f访问节点 {node}当前遍历顺序: {traversal_order}) for neighbor in range(n): if adj_matrix[node][neighbor] 1 and neighbor not in visited: print(f从 {node} 探索到 {neighbor}) _dfs(neighbor) print(f回溯到 {node}) _dfs(start) return traversal_order print(DFS遍历顺序:, dfs(adj_matrix, 0))运行这段代码控制台会输出详细的探索过程访问节点 0当前遍历顺序: [0] 从 0 探索到 1 访问节点 1当前遍历顺序: [0, 1] 从 1 探索到 3 访问节点 3当前遍历顺序: [0, 1, 3] 从 3 探索到 4 访问节点 4当前遍历顺序: [0, 1, 3, 4] 从 4 探索到 2 访问节点 2当前遍历顺序: [0, 1, 3, 4, 2] 回溯到 4 从 4 探索到 5 访问节点 5当前遍历顺序: [0, 1, 3, 4, 2, 5] 回溯到 4 回溯到 3 回溯到 1 从 1 探索到 6 访问节点 6当前遍历顺序: [0, 1, 3, 4, 2, 5, 6] 回溯到 1 回溯到 0 DFS遍历顺序: [0, 1, 3, 4, 2, 5, 6]通过这个输出我们可以清晰地看到DFS是如何一步步深入图中直到无法继续前进时才回溯的。这种可视化方式比单纯记忆遍历顺序要直观得多。3. 广度优先搜索(BFS)层层递进的探索与DFS的纵深策略不同广度优先搜索采用广撒网的方式先访问离起点最近的顶点再逐步向外扩展。这种特性使BFS非常适合寻找最短路径问题。3.1 BFS的核心思想BFS算法的关键特点包括使用队列数据结构来管理待访问顶点先访问顶点的所有邻居再访问邻居的邻居保证先访问离起点更近的顶点BFS的实现通常需要以下组件visited集合记录已访问顶点队列存储待访问顶点traversal_order列表记录最终的遍历顺序3.2 BFS的Python实现与逐步解析让我们同样从顶点0出发实现BFS遍历from collections import deque def bfs(adj_matrix, start): n len(adj_matrix) visited set([start]) queue deque([start]) traversal_order [] while queue: node queue.popleft() traversal_order.append(node) print(f访问节点 {node}当前遍历顺序: {traversal_order}) for neighbor in range(n): if adj_matrix[node][neighbor] 1 and neighbor not in visited: visited.add(neighbor) queue.append(neighbor) print(f发现 {node} 的邻居 {neighbor} 加入队列) return traversal_order print(BFS遍历顺序:, bfs(adj_matrix, 0))运行结果展示了BFS的层次遍历特性访问节点 0当前遍历顺序: [0] 发现 0 的邻居 1 加入队列 发现 0 的邻居 2 加入队列 发现 0 的邻居 6 加入队列 访问节点 1当前遍历顺序: [0, 1] 发现 1 的邻居 3 加入队列 访问节点 2当前遍历顺序: [0, 1, 2] 访问节点 6当前遍历顺序: [0, 1, 2, 6] 访问节点 3当前遍历顺序: [0, 1, 2, 6, 3] 发现 3 的邻居 4 加入队列 访问节点 4当前遍历顺序: [0, 1, 2, 6, 3, 4] 发现 4 的邻居 5 加入队列 访问节点 5当前遍历顺序: [0, 1, 2, 6, 3, 4, 5] BFS遍历顺序: [0, 1, 2, 6, 3, 4, 5]从输出可以看出BFS确实是一层一层地探索图先访问所有直接邻居再访问邻居的邻居。这种遍历顺序保证了我们能首先找到从起点到任何顶点的最短路径。4. DFS与BFS的对比与应用场景理解了两种算法的实现后我们需要知道它们各自的适用场景。下面这个对比表格清晰地展示了两者的区别特性DFSBFS数据结构栈(递归调用栈)队列空间复杂度O(h)h为图的最大深度O(w)w为图的最大宽度遍历顺序深度优先广度优先是否找到最短路径否是适用场景拓扑排序、连通分量、路径存在性最短路径、社交网络中的好友推荐4.1 何时选择DFSDFS在以下场景中表现更优检查图中是否存在环路进行拓扑排序查找图中的所有连通分量解决迷宫问题(寻找任何一条路径)4.2 何时选择BFSBFS则更适合这些场景查找未加权图中的最短路径社交网络中的好友推荐(三度人脉等)网络爬虫的页面抓取策略查找两个顶点之间的最短连接5. 算法优化与常见问题掌握了基础实现后我们可以进一步优化算法并了解一些常见问题。5.1 非递归实现DFS递归实现的DFS虽然简洁但在处理大规模图时可能会遇到栈溢出问题。我们可以用显式栈来实现非递归版本def dfs_iterative(adj_matrix, start): n len(adj_matrix) visited set() stack [start] traversal_order [] while stack: node stack.pop() if node not in visited: visited.add(node) traversal_order.append(node) print(f访问节点 {node}当前遍历顺序: {traversal_order}) # 注意反向压栈以保证正确的访问顺序 for neighbor in reversed(range(n)): if adj_matrix[node][neighbor] 1 and neighbor not in visited: stack.append(neighbor) return traversal_order5.2 处理不连通图前面的实现假设图是连通的。如果图不连通我们需要修改算法以遍历所有顶点def traverse_all(adj_matrix, traversal_func): n len(adj_matrix) visited set() result [] for node in range(n): if node not in visited: result traversal_func(adj_matrix, node, visited) return result # 修改DFS和BFS函数接受visited集合作为参数5.3 性能考量对于不同的图表示方式算法性能也有所不同邻接矩阵查找邻居需要O(V)时间(V为顶点数)邻接表查找邻居只需O(degree(V))时间因此对于稀疏图(边较少)邻接表表示更为高效而对于稠密图邻接矩阵可能更合适。