一句话定义
BFS 用队列按距起点的边数分层扩展,在无权图或相同正权的图中得到最少边数路径。入队时标记可避免重复扩展。
为什么重要
- 无权最短路径:迷宫最少步数、社交网络“几度好友”、网页爬虫按层抓取。
- 二叉树的层序遍历就是 BFS(见 k2.ds.binary-tree)。
- 是 Dijkstra 的“特例”:所有边权相等时,Dijkstra 退化为 BFS(见 k2.algo.dijkstra)。
使用边界
O(V+E) 适用于邻接表且每个节点只进入一次的常规图遍历;隐式状态空间中节点可能指数增长。BFS 与等权 Dijkstra 的距离结果一致,不表示二者的实现或开销相同。
原理 / 图解
时间复杂度 :每个顶点入队一次,每条边检查一次。
BFS 的早期描述之一见 E. F. Moore 1959 年的迷宫最短路径论文;概述:https://en.wikipedia.org/wiki/Breadth-first_search
可运行示例
网格迷宫最短路径(含路径还原与 ASCII 可视化)、社交网络“几度好友”(Python 3.15.0 一稿运行记录):
# 文件:examples/22_bfs.py
# 广度优先搜索 BFS:一圈一圈向外扩展(队列)。无权图中找到的就是最短路径
from collections import deque
grid = ["S.#.....",
".##.###.",
"....#...",
".##...#G"]
R, C = len(grid), len(grid[0])
start = next((r, c) for r in range(R) for c in range(C) if grid[r][c] == "S")
goal = next((r, c) for r in range(R) for c in range(C) if grid[r][c] == "G")
def bfs(start, goal):
q, parent = deque([start]), {start: None}
order = 0
while q:
cur = q.popleft(); order += 1
if cur == goal: break
r, c = cur
for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#" and (nr, nc) not in parent:
parent[(nr, nc)] = cur; q.append((nr, nc))
path, p = [], goal
while p: path.append(p); p = parent.get(p)
return path[::-1], order
path, visited = bfs(start, goal)
print(f"最短路径长度 {len(path)-1} 步,共出队 {visited} 个格子")
canvas = [list(row) for row in grid]
for r, c in path[1:-1]: canvas[r][c] = "*"
print("\n".join("".join(row) for row in canvas))
# 社交网络:几度好友(按层 BFS)
friends = {"你": ["A", "B"], "A": ["C"], "B": ["C", "D"], "C": ["E"], "D": [], "E": []}
dist, q = {"你": 0}, deque(["你"])
while q:
u = q.popleft()
for v in friends[u]:
if v not in dist: dist[v] = dist[u] + 1; q.append(v)
print("几度好友:", dist)
一稿留存输出:
最短路径长度 12 步,共出队 21 个格子
S.#.....
*##.###.
****#***
.##***#G
几度好友: {'你': 0, 'A': 1, 'B': 1, 'C': 2, 'D': 2, 'E': 3}
图中 * 是 BFS 找到的 12 步最短路径,# 是墙。BFS 只出队了 21 个格子就找到了终点。
常见误区
- 出队时才标记已访问:同一节点可能被多次入队,浪费时间甚至爆内存;应在入队时标记。
- 用 list.pop(0) 当队列:,改用
deque.popleft()。 - 在有权图上用 BFS 求最短路:BFS 只数边数,不看权重,结果会错(见 k2.algo.shortest-path 示例)。
- 忘记记录前驱节点:只能得到距离,无法还原路径。
与 AI 开发的关系
- 知识图谱多跳检索:从实体出发 1 跳、2 跳扩展邻居,作为 GraphRAG 的候选上下文。
- 网页爬取与数据采集:按层抓取站点(务必遵守 robots.txt 与网站条款)。
- Agent 搜索:在有限步数内按层枚举工具调用或状态,找最短操作序列。
- 依赖分析:找出一个模块变更会影响的所有下游(按层扩散)。
延伸阅读
- 维基百科:广度优先搜索 https://en.wikipedia.org/wiki/Breadth-first_search
- VisuAlgo 图遍历动画:https://visualgo.net/en/dfsbfs
- Red Blob Games:寻路算法图解 https://www.redblobgames.com/pathfinding/a-star/introduction.html
理解检查
把边数最少的路径当作时间最短的路径,需要什么条件?
参考答案:所有边代表相同的正时间成本;权重不等时应换用适合的加权最短路算法。
核验与复现
核验日期:2026-10-14。示例状态:运行通过。本轮日志:22_bfs.py。
配套代码与核验资料