广度优先搜索（BFS）——像水波一样扩散
中等2广度优先搜索（BFS）——像水波一样一层层找
广度优先搜索（BFS）是一种层层扩散的搜索方式。它像你在平静的池塘里扔下一块石头，波纹会一圈一圈向外扩散——先扩散到最近的一圈，再扩散到第二圈、第三圈……BFS 的主要用途是从起点出发，找到离起点最近的目标，比如在迷宫中找最短路径、在社交网络中找关系最近的朋友。
? 水波扩散 —— BFS 的核心思想
假设你站在操场中央，不小心把钥匙掉在草地上。你不想盲目乱跑，最好的办法是：先看自己脚下周围1米（第一圈），没有的话再看周围2米（第二圈），再看3米……这样你最先捡到的钥匙一定是离你最近的那把。
在计算机里，BFS 也是这样工作的：
- 从起点开始，把它所有相邻的节点（第一层）先全部看一遍。
- 如果第一层没有目标，就继续看第二层（第一层节点的邻居）。
- 一层一层向外，直到找到目标或搜完所有节点。
核心规则：BFS 保证找到的目标是层数最少的（也就是离起点“最近”的）。
生活中的例子对比
| 场景 | BFS 做法 | DFS 做法 |
|---|---|---|
| 找钥匙 | 先看一圈，再扩大一圈 | 沿一个方向走到头，不行再折返 |
| 找医生朋友 | 先问直系好友，再问好友的好友 | 先问一个好友，再问他的好友，一直问到最远 |
| 玩迷宫游戏 | 同时尝试所有岔路走一步 | 一条路走到黑再换 |
? 用队列实现 —— 就像排队买奶茶
BFS 用队列（queue）来模拟“一层一层”的过程。队列的特点是先进先出（FIFO），就像排队买奶茶：先来的人先买到，后来的人排在后边。
具体步骤：
- 把起点放入队列（排第一个）。
- 从队列中取出最前面的节点（popleft）。
- 检查这个节点是不是目标，如果是就结束。
- 如果不是，把它的所有未访问过的邻居都加到队列末尾（就像新来的人排到队尾）。
- 重复第 2~4 步，直到队列为空（说明所有节点都找过了）。
为了不走回头路，还需要一个访问记录（visited），就像你去过的房间会贴个标签“已查过”，避免重复走。
? Python 代码实现（基本版）
下面用代码展示 BFS 遍历一个图。图用“字典（邻接表）”表示，每个节点对应一个邻居列表。
from collections import deque
# 图用字典表示：键是节点，值是邻居列表
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
def bfs(graph, start, target):
queue = deque([start]) # 把起点放入队列
visited = set([start]) # 记录已经访问过的节点
while queue:
node = queue.popleft() # 取出队首节点
print(f"访问节点: {node}")
if node == target:
print(f"找到了目标: {target}")
return True
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # 标记已访问
queue.append(neighbor) # 邻居入队（排到队尾）
return False
bfs(graph, "A", "F")
输出解释：
从“A”开始，先访问第一层邻居“B”和“C”（注意顺序是 B 先，C 后），然后访问第二层“D”“E”“F”，最终找到“F”。因为“F”在第二层就被找到了，所以它是离 A 最近的 F（实际上 A→C→F 只有两步）。
? BFS 的另一大用途 —— 找到最短路径
如果不仅想知道“有没有目标”，还想知道最短路径具体怎么走，我们可以稍微改改代码：用字典记录每个节点是从哪个节点过来的（前驱节点），最后回溯路径。
比如还是上面的图，从 A 到 F 的最短路径是 A→C→F（两步）或 A→B→E→F（三步），BFS 会找到更短的那个。
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}
def bfs_shortest_path(graph, start, target):
queue = deque([start]) # 起点入队
visited = set([start]) # 已访问集合
parent = {start: None} # 记录每个节点的“父亲”
while queue:
node = queue.popleft() # 取出队首
if node == target:
# 回溯路径
path = []
while node is not None:
path.append(node)
node = parent[node]
path.reverse() # 反转得到从起点到目标的顺序
print(f"找到最短路径: {'→'.join(path)}")
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node # 记录 neighbor 是从 node 来的
queue.append(neighbor)
print("没有找到目标")
return None
bfs_shortest_path(graph, "A", "F")
输出：找到最短路径: A→C→F
注意：BFS 之所以能保证最短，是因为我们一层一层推进，第一次碰到目标时，一定是在最少层数里碰到的。
⚠️ 新手容易犯的错误
错误1：忘记标记已访问节点
# 错误写法
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
queue.append(neighbor) # ❌ 没检查是否访问过
后果：节点会被反复放入队列，导致死循环，或者无限输出。
正确做法：每次放入队列前先检查 if neighbor not in visited，并立即标记。
错误2：把队列和栈搞混
BFS 用 popleft()（从左边弹出），DFS 用 pop()（从右边弹出）。如果用了 pop()，实际上变成了深度优先搜索。
错误3：认为 BFS 只能用在图里
BFS 的思想同样适用于树、迷宫网格、状态空间（比如数字华容道）。只要能把问题抽象成“节点”和“邻居”，就能用 BFS。
? 完整示例 —— 在网格迷宫中找最短路径
假设有一个 5×5 的迷宫，0 表示空地，1 表示墙。从左上角 (0,0) 出发，走到右下角 (4,4)。每次可以上下左右走一步，不能穿墙。BFS 能找出最短路径。
from collections import deque
# 迷宫：0=空地，1=墙
maze = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0]
]
start = (0, 0) # 起点坐标
target = (4, 4) # 终点坐标
def bfs_maze(maze, start, target):
rows = len(maze)
cols = len(maze[0])
queue = deque([start]) # 起点入队
visited = set([start]) # 访问过的格子
parent = {start: None} # 记录前驱
# 四个方向：上、下、左、右
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while queue:
row, col = queue.popleft() # 当前格子
if (row, col) == target:
# 回溯路径
path = []
cur = (row, col)
while cur is not None:
path.append(cur)
cur = parent[cur]
path.reverse()
print(f"最短路径长度: {len(path)-1} 步")
print("路径:", path)
return path
for dr, dc in directions:
nr, nc = row + dr, col + dc
# 检查是否越界、是否是墙、是否已访问
if 0 <= nr < rows and 0 <= nc < cols:
if maze[nr][nc] == 0 and (nr, nc) not in visited:
visited.add((nr, nc))
parent[(nr, nc)] = (row, col)
queue.append((nr, nc))
print("无法到达目标")
return None
bfs_maze(maze, start, target)
输出：
最短路径长度: 8 步
路径: [(0,0), (0,1), (1,1), (2,1)? 等等，这里实际走法不唯一，但 BFS 会给出最短的一条。
? 相关知识点指引
- 深度优先搜索（DFS）：BFS 的兄弟，适合“一条路走到黑”的场景（比如判断连通性、拓扑排序）。
- 队列（deque）：BFS 的核心数据结构，建议学习
collections.deque的用法（append、popleft）。 - 图（Graph）：BFS 是图算法的基础，之后学 Dijkstra（加权最短路径）、A* 等都离不开它。
- 双向 BFS：当起点和终点都知道时，可以两边同时 BFS，速度更快（比如单词接龙问题）。
BFS 非常强大，遇到“最近”、“最少步数”、“最短路径”这类问题时，先想想能不能把问题画成图，然后用 BFS 解决。像水波一样扩散的思路，不仅用在程序里，生活中排队、查地图时也能用到哦！
例题精讲
在广度优先搜索（BFS）中，通常使用哪种数据结构来存储待访问的节点？
在无权图中，广度优先搜索（BFS）一定能够找到从起点到终点的最短路径（按边数计算）。
以下BFS函数用于遍历一个无向图（邻接表表示），请填写缺失的代码，使其正确工作。
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
___
___
关于广度优先搜索（BFS）和深度优先搜索（DFS）的比较，下列说法正确的是：
在5×5的网格中，0表示空地，1表示障碍物，从起点(0,0)到终点(4,4)只能上下左右移动。以下BFS代码求最短步数，请补充方向数组。
from collections import deque
def min_steps(grid):
n, m = 5, 5
visited = [[False]*m for _ in range(n)]
q = deque()
q.append((0,0,0)) # (x, y, step)
visited[0][0] = True
dirs = ___
while q:
x, y, step = q.popleft()
if x == 4 and y == 4:
return step
for dx, dy in dirs:
nx, ny = x+dx, y+dy
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny]==0:
visited[nx][ny] = True
q.append((nx, ny, step+1))
return -1