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

一、什么是广度优先搜索（BFS）？

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图、树的算法。其核心策略是：从起始节点出发，先访问所有直接邻居（第1层），再访问邻居的邻居（第2层），以此类推，逐层向外扩展，直到所有可达节点都被访问。

1.1 核心思想（三步走）

1. 访问起点：将起始节点标记为已访问，加入队列
2. 逐层扩展：从队列中取出节点，访问其所有未访问的邻居，加入队列
3. 重复直到队列为空：当队列为空时，遍历结束

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（右）的遍历顺序差异：

• BFS：A → B → C → D → E → F（逐层扩展）
• DFS：A → B → D → E → C → F（纵向深入）

二、BFS的数据结构支撑：队列（Queue）

BFS的实现必须依赖队列（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# 创建队列queue=deque()# 入队（添加到队尾）queue.append('A')queue.append('B')queue.append('C')# 出队（从队首取出）node=queue.popleft()# 取出 'A'print(queue)# deque(['B', 'C'])

为什么不使用list？

• list.pop(0)时间复杂度是O(n)，因为需要移动所有元素
• deque.popleft()时间复杂度是O(1)，效率更高

三、BFS遍历图

3.1 图的BFS遍历实现

fromcollectionsimportdequedefbfs(graph,start):visited=set([start])queue=deque([start])result=[]whilequeue:node=queue.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_result=bfs(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、C（A的邻居）
• 第3层：D、E、F、G（B和C的邻居，排除已访问的A）
• 第4层：H（E的邻居，排除已访问的B）

3.2 BFS遍历的队列状态变化

为了更直观理解BFS，我们来看看队列在每一步的变化：

四、BFS遍历二叉树（层序遍历）

4.1 二叉树的层序遍历

层序遍历是BFS在二叉树上的经典应用，它按从上到下、从左到右的顺序访问节点。

如上图所示，层序遍历顺序为：A → B → C → D → E → F → G → H → I

4.2 代码实现

fromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightdefbfs_level_order(root):ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.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 5root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print("" + "="*50)print("【示例2】二叉树的BFS层序遍历")print("="*50)print("二叉树结构:")print(" 1")print("/\")print(" 2 3")print("/\")print(" 4 5")levels=bfs_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):ifstart==end:return[start]visited=set([start])queue=deque([(start,[start])])whilequeue:node,path=queue.popleft()forneighboringraph.get(node,[]):ifneighbor==end: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,end='A','G'path=shortest_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 → G（4步，更长）
• A → C → F → G（3步，最短）

BFS保证找到的是步数最少的路径。

六、BFS经典实战：LeetCode 102. 二叉树的层序遍历

6.1 题目描述

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

6.2 解题思路

这是BFS在二叉树上的最直接应用，使用队列逐层处理节点。

6.3 代码实现

fromcollectionsimportdequedeflevelOrder(root):ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.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 7root2=TreeNode(3)root2.left=TreeNode(9)root2.right=TreeNode(20)root2.right.left=TreeNode(15)root2.right.right=TreeNode(7)print("" + "="*50)print("【示例4】LeetCode 102: 二叉树的层序遍历")print("="*50)print("二叉树结构:")print(" 3")print("/\")print(" 9 20")print("/\")print(" 15 7")result=levelOrder(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(b^{d)优化到O(b}(d/2))，其中b是分支因子，d是最短路径长度。

7.2 双向BFS实现

defbidirectional_bfs(graph,start,end):ifstart==end:return[start]queue_start=deque([(start,[start])])queue_end=deque([(end,[end])])visited_start={start:[start]}visited_end={end:[end]}whilequeue_startandqueue_end:iflen(queue_start)>len(queue_end):queue_start,queue_end=queue_end,queue_start visited_start,visited_end=visited_end,visited_startfor_inrange(len(queue_start)):node,path=queue_start.popleft()forneighboringraph.get(node,[]):ifneighborinvisited_end:returnpath+visited_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)path=bidirectional_bfs(path_graph,'A','G')print(f"双向BFS找到的最短路径:{' -> '.join(path)}")

八、BFS常见陷阱与避坑指南

8.1 陷阱1：入队后才标记访问

# 错误示例：会导致节点重复入队！queue=deque([start])whilequeue:node=queue.popleft()visited.add(node)# 出队时才标记！forneighboringraph[node]:ifneighbornotinvisited:queue.append(neighbor)# 正确做法：入队时立即标记queue=deque([start])visited.add(start)whilequeue:node=queue.popleft()forneighboringraph[node]:ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)

原因分析：

• 如果出队时才标记，一个节点可能在队列中存在多个副本
• 虽然最终结果正确，但队列规模会膨胀，效率降低

8.2 陷阱2：忘记处理孤立节点

# 错误：假设所有节点都连通# 正确：遍历所有节点，对每个未访问的节点启动BFSdefbfs_all_components(graph):visited=set()components=[]fornodeingraph:ifnodenotinvisited:component=bfs(graph,node)components.append(component)returncomponents

8.3 陷阱3：混淆BFS和DFS的应用场景

九、BFS总结

9.1 核心要点

BFS 广度优先搜索 数据结构：队列（Queue） 核心策略：横向扩展，层层推进 关键操作：入队 -> 出队 -> 访问邻居 -> 邻居入队 必备要素：visited集合（防重复）、deque（高效队列） 时间复杂度：O(V + E) 空间复杂度：O(w)，w为最大宽度 核心优势：天然支持最短路径（无权图）

9.2 BFS适用场景