Computing · Algorithms
Breadth-First Search (BFS)
广度优先搜索 (BFS)
~ 16 min · v15
广度优先搜索 BFS
cs-algo/graph-bfs · COMP2521 / 2041
0 / 5
1 一句话定义
BFS(广度优先搜索)就是从起点出发,先访问所有「一步能到」的点,再访问「两步能到」的点……一层一层往外扩,靠一个队列来记住"接下来该访问谁"。
把它想成往水里丢一颗石子:涟漪一圈圈向外扩散,近的先湿、远的后湿。BFS 就是这样按"距起点的层数"逐层推进。也正因为它先到的一定是最近的,BFS 能在无权图里求出最短路径(最少几条边)。它用队列(先进先出)排队:先排进去的点先被处理。
2 模型 · 单步看队列怎么驱动逐层扩散
BFS 的发动机是队列。点 ▶ 单步看:每次从队首取一个点处理,把它没访问过的邻居标记后塞到队尾。盯住右边的队列和每个点头顶的 dist(层号)。
BFS 的骨架(队列 + visited 数组)
三个零件:一个 visited[] 防重复、一个 queue 排队、一个 dist[] 记层号。
void bfs(Graph g, int src) { bool visited[V] = {false}; Queue q = queueNew(); visited[src] = true; enqueue(q, src); // 起点先入队并标记 while (!queueEmpty(q)) { int v = dequeue(q); // 取队首 printf("%d ", v); // ← 处理 v:打印/记录访问序/算距离(遍历的目的就在这步) for (int w : neighbours(v)) if (!visited[w]) { // 没访问过才处理 visited[w] = true; // 入队时立刻标记! enqueue(q, w); } } }
最关键的一行是 visited[w] = true 必须在入队时就做(而不是出队时)。否则同一个点会被多个邻居反复塞进队列,轻则重复访问、重则死循环——这正是 BFS 最经典的 bug。
BFS 遍历 · 源点 0
图(橙=正在处理,绿=已访问,蓝虚线=在队列里等)
队列 Queue(队首在左,先进先出)
已访问顺序
还没开始
代码(当前行高亮)
提示
点 ▶ 演示 BFS:看队列怎么"先进先出"地驱动一层层扩散,每个点头顶的数字是它到源点 0 的最短边数。
0
已访问
0
队列长度
—
当前层 dist
3 核心要点 · 4 句人话吃透 BFS
每张卡片先一句大白话。第①②条是 BFS 的本质,第③条是它最值钱的用途,第④条是最常翻车的坑。
① 队列 = BFS 的发动机
一句话:BFS 用队列(先进先出),先排进去的先处理,于是天然按"离起点的远近"一层层推进。
把 DFS 的栈换成队列,就从"一条道走到黑"变成"一圈圈向外扩"。队首总是当前最浅的待处理点,所以处理顺序严格按层。
② visited 数组 = 防重复 / 防死循环
一句话:每个点只入队一次。入队时立刻标 visited,之后别的邻居再想塞它就被挡下。
图里有环,不标记就会绕圈无限入队。标记的时机要在入队时,不是出队时——否则同一个点会被多个邻居重复入队。
③ 无权图最短路 = BFS 招牌
一句话:在每条边等长(无权)的图里,BFS 第一次到达某点时,走的就是最短路(边数最少)。
因为 BFS 按层扩散,先到达 = 层号最小 = 距离最短。记录
dist[w] = dist[v] + 1 就得到最短边数。词梯、骑士走棋、迷宫最短步数都是它。注意:带权图最短路要用 Dijkstra,不是 BFS。④ 复杂度 O(V + E)
一句话:每个顶点进出队列一次、每条边被看一次,所以是 O(V+E)(用邻接表)。
用邻接矩阵则是 O(V²),因为每个点都要扫一整行找邻居。所以稀疏图配邻接表跑 BFS 最划算。
4 错误实验室 · 点一下亲眼看 bug
下面 4 个是写 BFS 最常翻车的坑——忘标 visited 死循环、标记时机错、用栈写成了 DFS、把带权最短路也当 BFS 做。点击卡片看运行效果。
① 忘了标 visited
有环图里同一个点反复入队 → 死循环
② 出队时才标记
入队前没标 → 同一点被多次入队,重复处理
③ 用了栈而非队列
后进先出 → 变成 DFS,层序与最短路全错
④ 拿 BFS 求带权最短路
边有权重时 BFS 的"层数"不等于最短距离
// 点击上方任一卡片,查看错误代码与运行效果
$ ./a.out
(等待运行...)
5 即时小测 · 5 题 + 动手例题
这 5 题正对 BFS 套路:数据结构、最短路、visited 时机、复杂度、访问顺序。最后到练习系统亲手写 BFS。
去做例题:BFS · 可达顶点数 numReachable
去做例题