Computing · Algorithms

Breadth-First Search (BFS)

广度优先搜索 (BFS)

~ 16 min · v15

广度优先搜索 BFS

cs-algo/graph-bfs · COMP2521 / 2041
0 / 5

1 一句话定义

BFS(广度优先搜索)就是从起点出发,先访问所有「一步能到」的点,再访问「两步能到」的点……一层一层往外扩,靠一个队列来记住"接下来该访问谁"。

把它想成往水里丢一颗石子:涟漪一圈圈向外扩散,近的先湿、远的后湿。BFS 就是这样按"距起点的层数"逐层推进。也正因为它先到的一定是最近的,BFS 能在无权图里求出最短路径(最少几条边)。它用队列(先进先出)排队:先排进去的点先被处理。
第0层 第1层 第2层 第3层 0 1 2 3 4 5 从源点 0 一层层向外扩 → 每个点的层号 = 到 0 的最短边数
这正是下一节交互区的示例图。源点 0(橙)是第 0 层;1、2 是第 1 层;3、4 是第 2 层;5 是第 3 层。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
去做例题

⌨ 键盘快捷键

→
单步前进
←
单步后退
Space
播放 / 暂停
R
重置
?
打开本帮助