CC++ & Algorithm

广度优先搜索BFS

中等0
语言版本：C++
概述：像水波一圈一圈向外扩散，先找到的目标一定距离起点最近，这就是广度优先搜索。

广度优先搜索（BFS）——像水波一样层层扩散

什么是广度优先搜索？

想象一下，你往平静的湖面丢一颗小石子，波纹会一圈一圈向外扩散，最先碰到石子的水波一定是离石子最近的那一圈。广度优先搜索（BFS） 正是利用这个原理，像水波一样，从起点开始，先探索所有距离为1的邻居，再探索邻居的邻居（距离为2），一层一层往外推。如果你要找某个目标，最先找到的路径一定是步数最少的（也就是最短路径）。

在生活中，BFS 的应用随处可见：

  • 找朋友：你想知道你和某个明星之间通过朋友关系最少需要几个人介绍？从你开始，先问你的所有朋友，如果朋友里没有那个明星，再问朋友的朋友……这就是 BFS。
  • 走迷宫：从入口到出口，最少要走多少步？BFS 会帮你找到最短路径。
  • 网络游戏：在二维地图中，怪物如何找到前往玩家位置的最短路线？BFS 是其中一种基础算法。

下面我们通过一个具体的图，一步步理解 BFS 的原理和代码实现。

BFS 的核心思想：队列、已访问标记、距离记录

要实现 BFS，我们需要三样工具：

  1. 队列（Queue）：用来存放“待探索的节点”。BFS 先探索起点的邻居，然后探索邻居的邻居，所以必须先进先出（先放入队列的节点先被处理）。Python 的 collections.deque 可以实现高效的两端操作。
  2. 已访问集合（visited）：记录哪些节点已经访问过，防止走回头路，避免死循环。
  3. 距离字典（distance）：记录每个节点离起点的最短距离（步数）。每次发现一个新邻居，它的距离 = 当前节点距离 + 1。

举个例子：朋友圈关系图

假设我们有这样一个图，节点是朋友，连线表示两个人认识。

1 --- 2
|     |
3 --- 4 --- 5

节点1是你的起点，你想找节点5，最少需要经过几个人介绍？
从1出发，它的邻居是2和3（距离1）；然后从2和3出发，它们的邻居包括4（距离2）；最后从4出发，邻居包括5（距离3）。所以最短距离是 3 步（1→2→4→5 或 1→3→4→5）。

BFS 的代码实现（分步讲解）

下面用 Python 实现上面的图，用 BFS 找节点5，并打印最短距离。

from collections import deque

# 定义图：用字典表示，每个节点对应一个邻居列表
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3, 5],
    5: [4]
}

def bfs(start, target):
    queue = deque([start])          # 队列里放待探索的节点，起点先入队
    visited = {start}               # 已访问过的节点集合，起点标记为已访问
    distance = {start: 0}           # 记录每个节点离起点的距离，起点距离为0

    while queue:                    # 只要队列不为空，就继续探索
        node = queue.popleft()      # 取出队首节点（最先进入队列的）
        print(f"当前处理节点：{node}，距离起点：{distance[node]}")

        if node == target:          # 如果当前节点就是目标，输出距离并结束
            print(f"找到目标 {target}！最短距离为 {distance[node]}")
            return distance[node]

        # 遍历当前节点的所有邻居
        for neighbor in graph[node]:
            if neighbor not in visited:      # 只处理未访问过的邻居
                visited.add(neighbor)        # 标记为已访问
                distance[neighbor] = distance[node] + 1  # 距离加1
                queue.append(neighbor)       # 将邻居放入队尾，等待后续探索

    print(f"没有找到目标 {target}")
    return None

# 调用函数
bfs(1, 5)

运行过程可视化（理解队列如何工作）：

  • 初始：队列 = [1]，visited = {1}，distance = {1:0}
  • 弹出1，检查：不是目标，遍历邻居2和3，均未访问 → 入队2和3，distance[2]=1，distance[3]=1，visited增加{2,3}，队列变为 [2,3]
  • 弹出2，邻居1已访问，邻居4未访问 → 入队4，distance[4]=2，队列变为 [3,4]
  • 弹出3，邻居4已访问（因为从2已经加入），邻居1已访问 → 无新节点，队列变为 [4]
  • 弹出4，邻居2、3已访问，邻居5未访问 → 入队5，distance[5]=3，队列变为 [5]
  • 弹出5，发现是目标，输出距离3。

关键点解释

  • 队列的先进先出保证了“层层推进”：距离为1的节点2和3先入队，它们会先于距离为2的节点4被处理。这样，当我们第一次找到目标时，它一定是所有可能路径中步数最少的。
  • visited 为什么重要：如果没有 visited，从节点2访问邻居4后，从节点3访问邻居4时又会把4加入队列，导致重复处理，甚至死循环（如果图中有环）。
  • distance 的更新时机：只在第一次发现邻居时更新，这样每个节点的距离就是最短距离。因为 BFS 按层探索，第一次访问到某个节点时，路径一定是最短的。

新手常犯的错误

  1. 忘记标记 visited：导致节点被重复加入队列，不仅效率低，还可能造成队列爆炸或无限循环（尤其在有环的图中）。

    # 错误示例
queue.append(neighbor)
# 应该先标记 visited，再入队

  2. 队列操作错误：用了列表的 pop(0) 实现队列？Python 列表的 pop(0) 是 O(n) 操作，效率极低，应该用 collections.deque 的 popleft()。

    # 错误
queue = [start]
node = queue.pop(0)  # 慢！

  3. 距离更新错误：有时新手会用 distance[node] = distance.get(node, 0) + 1，但这样可能重复更新已存在的节点距离，导致距离被错误累加。正确做法是 只在第一次发现邻居时更新。

  4. 忽视图的表示方式：BFS 适用于任何可以用图表示的问题。如果是网格（迷宫），需要自己处理上下左右四个方向的邻居，别忘了边界检查。

  5. 没有考虑起点就是目标的情况：如果 start 等于 target，应该直接返回 0。上面的代码中，如果 start==target，在第一轮循环就会输出距离0。

完整示例：用 BFS 走迷宫（二维网格）

除了普通图，BFS 最经典的应用是走迷宫。我们来看一个具体例子：在 4x4 的网格中，从起点 (0,0) 走到终点 (3,3)，0 表示可走，1 表示障碍。

from collections import deque

# 迷宫：0可走，1障碍
maze = [
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [1, 0, 0, 0]
]

def bfs_maze(start, end):
    rows, cols = len(maze), len(maze[0])
    # 四个方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 队列存放 (行, 列) 坐标
    queue = deque([start])
    visited = {start}          # 已访问的坐标集合
    distance = {start: 0}      # 记录每个坐标离起点的距离

    while queue:
        row, col = queue.popleft()
        if (row, col) == end:
            print(f"到达终点，最短步数：{distance[(row, col)]}")
            return distance[(row, col)]

        # 尝试四个方向
        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            # 检查是否在迷宫范围内，是否可走，是否未访问
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                distance[(nr, nc)] = distance[(row, col)] + 1
                queue.append((nr, nc))

    print("无法到达终点")
    return None

# 调用
bfs_maze((0, 0), (3, 3))

运行结果：从 (0,0) 到 (3,3) 的最短步数为 6（可手算验证）。

总结与相关指引

  • BFS 的特点：适用于 无权图（每条边权重相同）中求最短路径，也适用于 状态空间搜索（如八数码、单词接龙）。
  • 时间复杂度：O(V + E)，其中 V 是节点数，E 是边数（每个节点和每条边都访问一次）。
  • 空间复杂度：O(V)，需要存储队列和 visited。

接下来可以学习：

  • 深度优先搜索（DFS）：使用栈（或递归），适合探索所有路径、拓扑排序等。
  • Dijkstra 算法：解决带权图的最短路径问题（权重非负）。
  • A 搜索*：在 BFS 基础上加入启发式函数，更快找到目标。

现在，你可以试着修改上面的迷宫代码，比如增加障碍物、改变起点终点，或者把图改成你身边的朋友关系，看看用 BFS 能不能帮你找到你和某个偶像之间最少需要几个人介绍！

例题精讲

1单选题

在广度优先搜索（BFS）算法中，通常使用哪种数据结构来存储待访问的节点？

A栈
B队列
C数组
D集合
2判断题

在无权图中，广度优先搜索（BFS）一定能找到从起点到终点的最短路径。

3填空题
以下是用BFS遍历图的Python代码片段，请补充缺失部分（使用collections.deque）。

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = ___
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                ___
4单选题

给定一个二维网格（0表示空地，1表示障碍物），从左上角(0,0)出发，每次只能向上、下、左、右移动一格，到达右下角(n-1,m-1)的最短路径长度是多少？若无法到达，返回-1。以下哪种算法最适合解决该问题？

A深度优先搜索（DFS）
B广度优先搜索（BFS）
C二分查找
D动态规划
5判断题

在广度优先搜索（BFS）中，所有节点的访问顺序是按照它们的深度（距离起点的边数）递增的。