第 40 课·图算法进阶

广度优先搜索（BFS）

bfsqueuelevelshortest

第40课 - 广度优先搜索（BFS）

学习目标

  1. 理解BFS的基本原理：掌握广度优先搜索的思想和工作机制
  2. 掌握队列在BFS中的应用：理解为什么队列是实现BFS的关键数据结构
  3. 实现BFS算法：能够编写基本的BFS代码解决图遍历问题
  4. 应用BFS解决实际问题：学会用BFS求解最短路径、层级遍历等问题

核心概念

什么是广度优先搜索？

想象你往池塘中央扔一块石头，波纹会以同心圆的方式向外扩散。广度优先搜索（BFS）就像这个波纹扩散的过程：从起点开始，先访问所有相邻节点，再逐层向外扩展，直到找到目标或遍历完整个图。

BFS的核心思想是“一层一层地搜索”，优先访问距离起点近的节点。这使得BFS特别适合解决“最短路径”问题（在无权图中）。

为什么需要队列？

BFS需要先进先出（FIFO） 的数据结构来记录待访问的节点。当我们访问一个节点时，会把它的所有邻居加入队列，然后从队列头部取出下一个要访问的节点。这样就能保证我们按层级顺序遍历。

graph LR
    A((起点)) --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    
    style A fill:#e1f5fe
    style B fill:#f3e5f5
    style C fill:#f3e5f5
    style D fill:#e8f5e8
    style E fill:#e8f5e8
    style F fill:#e8f5e8
    style G fill:#e8f5e8

访问顺序：A → B, C → D, E, F, G

BFS vs DFS（上节课内容）

  • BFS（广度优先）：使用队列，按层访问，适合最短路径问题
  • DFS（深度优先）：使用栈/递归，一条路走到底，适合连通性检查、路径搜索

代码示例

示例1：基本BFS实现

from collections import deque

def bfs(graph, start):
    """
    基本的BFS遍历实现
    
    参数:
        graph: 图的邻接表表示（字典）
        start: 起始节点
    
    返回:
        访问顺序列表
    """
    visited = set()      # 记录已访问的节点
    queue = deque()      # 使用队列存储待访问节点
    result = []          # 记录访问顺序
    
    # 将起始节点加入队列
    queue.append(start)
    visited.add(start)
    
    while queue:
        # 从队列头部取出节点
        node = queue.popleft()
        result.append(node)
        
        # 遍历当前节点的所有邻居
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# 创建示例图（邻接表）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

# 执行BFS
print("BFS遍历顺序:", bfs(graph, 'A'))

运行结果：

BFS遍历顺序: ['A', 'B', 'C', 'D', 'E', 'F', 'G']

示例2：带层级信息的BFS（最短路径）

from collections import deque

def bfs_level_order(graph, start):
    """
    BFS遍历，记录每个节点的层级（距离）
    
    参数:
        graph: 图的邻接表
        start: 起始节点
    
    返回:
        字典，键是节点，值是到起始节点的最短距离
    """
    visited = set()
    queue = deque()
    distance = {}  # 记录距离
    
    # 起始节点距离为0
    queue.append(start)
    visited.add(start)
    distance[start] = 0
    
    while queue:
        node = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                # 邻居的距离 = 当前节点距离 + 1
                distance[neighbor] = distance[node] + 1
    
    return distance

# 使用上面相同的图
print("各节点到A的最短距离:")
distances = bfs_level_order(graph, 'A')
for node, dist in distances.items():
    print(f"  {node}: {dist}步")

运行结果：

各节点到A的最短距离:
  A: 0步
  B: 1步
  C: 1步
  D: 2步
  E: 2步
  F: 2步
  G: 2步

示例3：最短路径搜索

from collections import deque

def shortest_path_bfs(graph, start, end):
    """
    使用BFS寻找从start到end的最短路径
    
    参数:
        graph: 图的邻接表
        start: 起始节点
        end: 目标节点
    
    返回:
        最短路径列表，如果不可达则返回空列表
    """
    if start == end:
        return [start]
    
    visited = set()
    queue = deque()
    parent = {}  # 记录每个节点的父节点（用于重建路径）
    
    queue.append(start)
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        
        # 找到目标节点
        if node == end:
            # 重建路径
            path = []
            current = end
            while current != start:
                path.append(current)
                current = parent[current]
            path.append(start)
            return path[::-1]  # 反转得到从起点到终点的路径
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                parent[neighbor] = node  # 记录父节点
    
    return []  # 不可达

# 测试最短路径
path = shortest_path_bfs(graph, 'A', 'G')
print(f"从A到G的最短路径: {' → '.join(path)}")
print(f"路径长度: {len(path)-1}步")

运行结果：

从A到G的最短路径: A → C → G
路径长度: 2步

实践练习

练习1：层序遍历二叉树（简单）

题目：给定一个二叉树，返回其节点值的层序遍历（逐层从左到右访问）。

输入：

# 二叉树结构
#       3
#      / \
#     9   20
#        /  \
#       15   7

tree = {
    3: [9, 20],
    9: [],
    20: [15, 7],
    15: [],
    7: []
}
root = 3

要求：实现 level_order_traversal(tree, root) 函数 预期输出：[[3], [9, 20], [15, 7]]

提示：需要在BFS中记录每一层的节点

练习2：网格中的最短路径（中等）

题目：在一个二维网格中，0表示可通行，1表示障碍物。从左上角(0,0)出发，找到到右下角(m-1,n-1)的最短路径长度。

输入：

grid = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]

要求：实现 shortest_path_in_grid(grid) 函数 预期输出：最短路径长度为6

提示：将网格视为图，每个格子是一个节点，只能上下左右移动

练习3：单词接龙（困难）

题目：给定两个单词（beginWord和endWord）和一个字典，找到从beginWord到endWord的最短转换序列的长度。

规则：

  1. 每次只能转换一个字母
  2. 转换后的单词必须在字典中

输入：

beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

要求：实现 ladder_length(beginWord, endWord, wordList) 函数 预期输出：5（hit → hot → dot → dog → cog）

提示：使用BFS搜索，每次改变单词的一个字母

常见错误

1. 忘记标记已访问节点

# 错误示例
def bfs_wrong(graph, start):
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            # 错误：没有检查是否已访问！
            queue.append(neighbor)
    
    return result
# 这会导致无限循环！

正确做法：始终维护一个visited集合，加入队列前先检查

2. 队列操作错误

# 错误示例
queue = deque()
queue.append(1)
queue.append(2)

# 错误：使用pop()而不是popleft()
first = queue.pop()  # 返回2，不是1！
# BFS需要先进先出，必须用popleft()

3. 忽略边界情况

# 错误：没有处理起点就是终点的情况
def shortest_path_wrong(graph, start, end):
    if not graph[start]:  # 只检查起点是否有邻居
        return []
    # 应该先检查start == end

4. 在有向图中错误地构建图

# 错误示例：有向图中错误地添加双向边
directed_graph = {
    'A': ['B'],
    'B': ['A'],  # 错误！如果A→B是有向的，B不应该直接指向A
}

5. 内存溢出（图过大时）

对于非常大的图，BFS可能需要存储大量节点在队列中。解决方案：

  • 使用迭代加深的BFS（IDDFS）
  • 考虑双向BFS
  • 在必要时使用启发式搜索（如A*）

小结

关键要点回顾

  1. BFS核心思想：像波纹一样一层一层扩展，先访问所有相邻节点
  2. 关键数据结构：使用队列实现先进先出，保证按层遍历
  3. 时间复杂度：O(V + E)，其中V是顶点数，E是边数
  4. 空间复杂度：O(V)，最坏情况下需要存储所有顶点

BFS的应用场景

  1. 最短路径问题：在无权图中找最短路径
  2. 层级遍历：二叉树层序遍历、图的层序遍历
  3. 连通性检查：判断两点是否连通（也可以用DFS）
  4. 社交网络分析：找朋友的朋友（N度人脉）
  5. 搜索引擎：网页爬取（按深度限制）

何时选择BFS？

✅ 当需要最短路径时（无权图）
✅ 当图的深度很大但广度有限时
✅ 需要按层处理问题时

❌ 当图的广度很大时（队列可能太大）
❌ 当不需要最短路径，只需判断是否存在路径时（DFS可能更高效）

下一步学习建议

  1. 尝试实现双向BFS，进一步提升性能
  2. 学习Dijkstra算法（解决带权图的最短路径）
  3. 了解A*算法（启发式搜索）

记住：BFS和DFS是图算法的基石，掌握它们后，很多复杂问题都可以迎刃而解！

下一课预告：第41课《拓扑排序》- 学习如何对有向无环图（DAG）进行线性排序，应用于任务调度、课程安排等场景。

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「拓扑排序」 以巩固所学知识。