1. 引言在图论和树形结构的遍历与搜索中深度优先搜索DFS、广度优先搜索BFS以及01BFS是三种基础且至关重要的算法。它们不仅是解决许多经典问题如路径查找、连通性判断、最短路径等的核心工具也是理解更复杂算法如Dijkstra、A*的基石。本文将深入剖析这三种算法的原理、实现、应用场景及性能差异并通过代码示例帮助读者建立清晰的认识。2. 深度优先搜索DFS2.1 核心思想与实现深度优先搜索遵循“一条路走到黑碰壁再回头”的策略。它从起始节点出发尽可能深地探索图的分支直到当前路径上的所有节点都被访问过然后回溯到上一个分叉点选择另一条未探索的路径继续深入。递归实现隐式栈def dfs_recursive(graph, node, visited): if node not in visited: visited.add(node) print(node) # 处理节点 for neighbor in graph[node]: dfs_recursive(graph, neighbor, visited) 示例图邻接表 graph { A: [B, C], B: [D, E], C: [F], D: [], E: [F], F: [] } visited set() dfs_recursive(graph, A, visited)迭代实现显式栈def dfs_iterative(graph, start): visited set() stack [start] while stack: node stack.pop() if node not in visited: visited.add(node) print(node) # 处理节点 # 注意为了与递归顺序一致邻接节点需逆序入栈 for neighbor in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor)2.2 时间复杂度与空间复杂度时间复杂度O(V E)其中 V 为顶点数E 为边数。每个顶点和每条边最多被访问一次。空间复杂度O(V)主要消耗在递归调用栈递归实现或显式栈迭代实现以及访问标记集合上。2.3 典型应用场景拓扑排序用于有向无环图DAG的任务调度。连通分量检测判断无向图的连通性或寻找有向图的强连通分量配合Kosaraju或Tarjan算法。路径查找与回溯如迷宫求解、八皇后问题、数独等。环检测在遍历过程中判断图中是否存在环。3. 广度优先搜索BFS3.1 核心思想与实现广度优先搜索采用“层层推进”的策略。它从起始节点开始先访问所有直接相邻的节点第一层然后再访问这些相邻节点的相邻节点第二层以此类推直到遍历完所有可达节点。迭代实现队列from collections import deque def bfs(graph, start): visited set([start]) queue deque([start]) while queue: node queue.popleft() print(node) # 处理节点 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)3.2 时间复杂度与空间复杂度时间复杂度O(V E)与DFS相同。空间复杂度O(V)队列在最坏情况下可能需要存储所有顶点。3.3 典型应用场景无权图最短路径BFS首次访问到目标节点时经过的路径就是最短路径边权为1。层次遍历如二叉树的层序遍历社交网络中的“好友度”计算。广播网络模拟消息或病毒在网络中的传播过程。迷宫最短路径在网格迷宫中寻找从起点到终点的最短步数。4. 01BFS0-1广度优先搜索4.1 核心思想与实现01BFS是BFS的一种变体专门用于处理边权只有两种可能值通常为0和1的图。它使用一个双端队列deque来保证始终以距离起点的非递减顺序处理节点从而在线性时间内求出最短路径。算法步骤初始化距离数组dist起点距离为0其他为无穷大。使用双端队列deque将起点加入队列。当队列不为空时弹出队首节点u。遍历u的所有邻接边(u, v, w)其中w为边权0或1。如果dist[u] w dist[v]则更新dist[v] dist[u] w。若w 0将v加入队首保证优先处理距离更小的节点。若w 1将v加入队尾。Python实现from collections import deque def zero_one_bfs(graph, start): graph: 邻接表graph[u] [(v, weight), ...]weight为0或1 n len(graph) dist [float(inf)] * n dist[start] 0 dq deque([start]) while dq: u dq.popleft() for v, w in graph[u]: if dist[u] w lt; dist[v]: dist[v] dist[u] w if w 0: dq.appendleft(v) # 权值为0加入队首 else: dq.append(v) # 权值为1加入队尾 return dist/code/pre 4.2 时间复杂度与空间复杂度 时间复杂度O(V E)每个节点和每条边最多被处理一次。 空间复杂度O(V)用于存储距离数组和双端队列。 4.3 典型应用场景 网格迷宫带成本移动某些方向移动代价为0如直行某些方向代价为1如转弯。 电路布线在网格上布线穿过某些区域如已有线路代价为0穿过空白区域代价为1。 双端队列优化的最短路径任何边权仅为0或1的图的最短路径问题。 5. 三种算法对比 特性 DFS BFS 01BFS 数据结构 栈递归/迭代 队列 双端队列deque 遍历顺序 深度优先 广度优先层序 按距离非递减0权优先 最短路径 不保证无权图 保证无权图 保证0-1权图 空间开销 O(树高) / O(V) O(最宽层) / O(V) O(V) 适用图类型 通用 通用 边权仅为0或1 经典问题 回溯、拓扑排序、连通分量 层序遍历、无权图最短路径 0-1权图最短路径、网格转弯问题 6. 总结与选择建议 DFS、BFS和01BFS各有其擅长的领域 需要探索所有可能解或进行回溯如排列组合、迷宫所有路径优先考虑DFS。 寻找最短步数或最近关系如社交网络好友度、无权图最短路径使用BFS。 图中边权只有0和1且需要求最短路径01BFS是最优选择其效率高于通用的Dijkstra算法。 理解这三种基础算法的内在联系与区别是迈向更高级图论算法如Dijkstra、Bellman-Ford、A*的关键一步。在实际编码面试或项目开发中根据问题特征快速准确地选择并实现合适的搜索算法是程序员必备的核心能力。
