Python算法基础篇之广度优先搜索（BFS）

一、什么是广度优先搜索BFS广度优先搜索Breadth-First Search, BFS是一种用于遍历或搜索图、树的算法。其核心策略是从起始节点出发先访问所有直接邻居第1层再访问邻居的邻居第2层以此类推逐层向外扩展直到所有可达节点都被访问。1.1 核心思想三步走访问起点将起始节点标记为已访问加入队列逐层扩展从队列中取出节点访问其所有未访问的邻居加入队列重复直到队列为空当队列为空时遍历结束1.2 形象比喻想象你在湖面上投下一颗石子涟漪从中心开始一圈一圈向外扩散先覆盖第1圈距离1再覆盖第2圈距离2每一圈的点都是同时被波及的这就是BFS的精髓——“层层推进齐头并进”。1.3 BFS遍历过程图解下面是一张BFS遍历过程的示意图展示了BFS如何逐层扩展如上图所示BFS从节点A出发第1层访问A的直接邻居 F、C第2层访问F和C的邻居 G、D、B第3层访问G的邻居 E以此类推直到所有节点都被访问1.4 BFS与DFS对比BFS和DFS是两种截然不同的遍历策略上图清晰展示了BFS左和DFS右的遍历顺序差异BFSA → B → C → D → E → F逐层扩展DFSA → B → D → E → C → F纵向深入二、BFS的数据结构支撑队列QueueBFS的实现必须依赖队列Queue这种数据结构。2.1 队列的特性队列是一种先进先出FIFO, First In First Out的数据结构最先放入的元素最先被取出就像排队买票先到的人先服务2.2 为什么BFS必须用队列BFS要求先发现的节点先处理这正好符合队列FIFO的特性节点A先被发现A的邻居B、C后被发现A先出队处理B、C后出队处理这样就保证了逐层的顺序2.3 Python中的队列实现Python中推荐使用collections.deque来实现队列因为它在两端操作都是O(1)时间复杂度fromcollectionsimportdeque# 创建队列queuedeque()# 入队添加到队尾queue.append(A)queue.append(B)queue.append(C)# 出队从队首取出nodequeue.popleft()# 取出 Aprint(queue)# deque([B, C])为什么不使用listlist.pop(0)时间复杂度是O(n)因为需要移动所有元素deque.popleft()时间复杂度是O(1)效率更高三、BFS遍历图3.1 图的BFS遍历实现fromcollectionsimportdequedefbfs(graph,start):visitedset([start])queuedeque([start])result[]whilequeue:nodequeue.popleft()result.append(node)print(node,end )# 将所有未访问的邻居加入队列尾部forneighboringraph.get(node,[]):ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)returnresult# 构建示例图邻接表表示graph{A:[B,C],B:[A,D,E],C:[A,F,G],D:[B],E:[B,H],F:[C],G:[C],H:[E]}print(*50)print(【示例1】图的BFS遍历)print(*50)print(图结构:,graph)print( BFS遍历顺序从A开始:)bfs_resultbfs(graph,A)print(f 遍历结果列表:{bfs_result})运行结果 【示例1】图的BFS遍历 图结构: {A: [B, C], B: [A, D, E], C: [A, F, G], D: [B], E: [B, H], F: [C], G: [C], H: [E]} BFS遍历顺序从A开始: A B C D E F G H 遍历结果列表: [A, B, C, D, E, F, G, H]BFS遍历顺序解析第1层A起点第2层B、CA的邻居第3层D、E、F、GB和C的邻居排除已访问的A第4层HE的邻居排除已访问的B3.2 BFS遍历的队列状态变化为了更直观理解BFS我们来看看队列在每一步的变化步骤当前节点队列状态已访问初始-[A]{A}1A[B, C]{A, B, C}2B[C, D, E]{A, B, C, D, E}3C[D, E, F, G]{A, B, C, D, E, F, G}4D[E, F, G]…5E[F, G, H]…6F[G, H]…7G[H]…8H[]全部访问四、BFS遍历二叉树层序遍历4.1 二叉树的层序遍历层序遍历是BFS在二叉树上的经典应用它按从上到下、从左到右的顺序访问节点。如上图所示层序遍历顺序为A → B → C → D → E → F → G → H → I4.2 代码实现fromcollectionsimportdequeclassTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightdefbfs_level_order(root):ifnotroot:return[]result[]queuedeque([root])whilequeue:level_sizelen(queue)current_level[]for_inrange(level_size):nodequeue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult# 构建示例二叉树# 1# / \# 2 3# / \# 4 5rootTreeNode(1)root.leftTreeNode(2)root.rightTreeNode(3)root.left.leftTreeNode(4)root.left.rightTreeNode(5)print( *50)print(【示例2】二叉树的BFS层序遍历)print(*50)print(二叉树结构:)print( 1)print(/\)print( 2 3)print(/\)print( 4 5)levelsbfs_level_order(root)print(f 层序遍历结果:{levels})print(解释: 第1层[1], 第2层[2,3], 第3层[4,5])运行结果 【示例2】二叉树的BFS层序遍历 二叉树结构: 1 / 2 3 / 4 5 层序遍历结果: [[1], [2, 3], [4, 5]] 解释: 第1层[1], 第2层[2,3], 第3层[4,5]关键点解析level_size len(queue)是分层的关键记录当前层的节点数内层循环只处理当前层的节点不会混入下一层的节点这种方法可以很方便地获取树的深度、每层的最大值等信息五、BFS的核心优势最短路径5.1 为什么BFS能找到最短路径BFS的逐层扩展特性有一个非常重要的性质第一次到达目标节点的路径一定是最短路径在无权图中。原因BFS按距离起点的远近顺序访问节点距离为1的节点先被访问距离为2的次之以此类推当第一次到达目标节点时走过的路径长度就是最短距离5.2 无权图最短路径实现fromcollectionsimportdequedefshortest_path(graph,start,end):ifstartend:return[start]visitedset([start])queuedeque([(start,[start])])whilequeue:node,pathqueue.popleft()forneighboringraph.get(node,[]):ifneighborend:returnpath[neighbor]ifneighbornotinvisited:visited.add(neighbor)queue.append((neighbor,path[neighbor]))returnNone# 测试图path_graph{A:[B,C],B:[A,D,E],C:[A,F],D:[B],E:[B,F],F:[C,E,G],G:[F]}print( *50)print(【示例3】BFS求最短路径)print(*50)print(图结构:,path_graph)start,endA,Gpathshortest_path(path_graph,start,end)print(f 从{start}到{end}的最短路径:{ - .join(path)})print(f路径长度:{len(path)-1}步)运行结果 【示例3】BFS求最短路径 图结构: {A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E, G], G: [F]} 从 A 到 G 的最短路径: A - C - F - G 路径长度: 3 步对比其他路径A → B → E → F → G4步更长A → C → F → G3步最短BFS保证找到的是步数最少的路径。六、BFS经典实战LeetCode 102. 二叉树的层序遍历6.1 题目描述给你一个二叉树请你返回其按层序遍历得到的节点值。即逐层地从左到右访问所有节点。6.2 解题思路这是BFS在二叉树上的最直接应用使用队列逐层处理节点。6.3 代码实现fromcollectionsimportdequedeflevelOrder(root):ifnotroot:return[]result[]queuedeque([root])whilequeue:level_sizelen(queue)current_level[]for_inrange(level_size):nodequeue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult# 构建更复杂的二叉树# 3# / \# 9 20# / \# 15 7root2TreeNode(3)root2.leftTreeNode(9)root2.rightTreeNode(20)root2.right.leftTreeNode(15)root2.right.rightTreeNode(7)print( *50)print(【示例4】LeetCode 102: 二叉树的层序遍历)print(*50)print(二叉树结构:)print( 3)print(/\)print( 9 20)print(/\)print( 15 7)resultlevelOrder(root2)print(f 层序遍历结果:{result})运行结果 【示例4】LeetCode 102: 二叉树的层序遍历 二叉树结构: 3 / 9 20 / 15 7 层序遍历结果: [[3], [9, 20], [15, 7]]七、BFS进阶双向BFS优化7.1 什么是双向BFS普通BFS从起点单向扩展到终点。双向BFS则从起点和终点同时开始BFS在中间相遇。优势将时间复杂度从O(bd)优化到O(b(d/2))其中b是分支因子d是最短路径长度。7.2 双向BFS实现defbidirectional_bfs(graph,start,end):ifstartend:return[start]queue_startdeque([(start,[start])])queue_enddeque([(end,[end])])visited_start{start:[start]}visited_end{end:[end]}whilequeue_startandqueue_end:iflen(queue_start)len(queue_end):queue_start,queue_endqueue_end,queue_start visited_start,visited_endvisited_end,visited_startfor_inrange(len(queue_start)):node,pathqueue_start.popleft()forneighboringraph.get(node,[]):ifneighborinvisited_end:returnpathvisited_end[neighbor][::-1][1:]ifneighbornotinvisited_start:visited_start[neighbor]path[neighbor]queue_start.append((neighbor,path[neighbor]))returnNoneprint( *50)print(【示例5】双向BFS优化)print(*50)print(图结构:,path_graph)pathbidirectional_bfs(path_graph,A,G)print(f双向BFS找到的最短路径:{ - .join(path)})八、BFS常见陷阱与避坑指南8.1 陷阱1入队后才标记访问# 错误示例会导致节点重复入队queuedeque([start])whilequeue:nodequeue.popleft()visited.add(node)# 出队时才标记forneighboringraph[node]:ifneighbornotinvisited:queue.append(neighbor)# 正确做法入队时立即标记queuedeque([start])visited.add(start)whilequeue:nodequeue.popleft()forneighboringraph[node]:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)原因分析如果出队时才标记一个节点可能在队列中存在多个副本虽然最终结果正确但队列规模会膨胀效率降低8.2 陷阱2忘记处理孤立节点# 错误假设所有节点都连通# 正确遍历所有节点对每个未访问的节点启动BFSdefbfs_all_components(graph):visitedset()components[]fornodeingraph:ifnodenotinvisited:componentbfs(graph,node)components.append(component)returncomponents8.3 陷阱3混淆BFS和DFS的应用场景问题类型正确选择原因求最短路径BFS逐层扩展第一次到达即最短求所有路径DFS需要遍历所有可能判断连通性均可两者都能完成拓扑排序DFS需要后序遍历九、BFS总结9.1 核心要点BFS 广度优先搜索 数据结构队列Queue 核心策略横向扩展层层推进 关键操作入队 - 出队 - 访问邻居 - 邻居入队 必备要素visited集合防重复、deque高效队列 时间复杂度O(V E) 空间复杂度O(w)w为最大宽度 核心优势天然支持最短路径无权图9.2 BFS适用场景场景说明典型题目最短路径无权图的最短路径迷宫问题、单词接龙层级分析按层处理节点二叉树层序遍历、N叉树层序遍历最近邻居找到距离最近的解社交网络中的最近共同好友扩散模型模拟传播过程病毒传播、颜色填充拓扑排序Kahn算法入度法课程表、任务调度