广度优先搜索（Breadth-First Search）

算法原理

广度优先搜索（BFS）是图上"按层扩散"的遍历：从源点出发，先访问所有距离为 1 的节点，再访问距离为 2 的节点……像水波一样一圈圈向外推。它靠一个 FIFO 队列保证层次顺序——"先被发现的先被处理"，这使它天然求出单源最短路径（无权图）：任何一个节点第一次被发现时的层数，就是它到源点的最少步数，之后再来多少条边都改写不了这个数。

本动画在 10 个节点、10 条边的无向图上演示完整一轮：主分量 8 个节点（含两个"双父"节点 D、G——两条边都能到，但只有先到的算数）加一对不可达节点 H–I（互连但与主图断开，BFS 到不了它们）。上区是图舞台，下区是 FIFO 队列条——队列是 BFS 的心脏，入队、出队、排队次序全部可见。

节拍（动画严格按此演示）：

源点入队：S 标记距离 d=0，进入队列；
出队：队头节点出队进入"处理中"，它的上一层邻居（父节点）此刻转为"已处理"绿色；
逐边检查：按字母序检查出队节点的每条邻边——邻居未发现 → 标记距离 d=k 入队（这条边成为 BFS 树边）；邻居已在队 → 拒绝（红闪：第二次到达不作数）；邻居已处理 → 跳过（父边在父端已查过，静默不占拍）；
队列空则遍历结束；到不了的节点距离永远停在 ?。

动画怎么看

橙描边节点：已发现、在队列里排队等处理（距离已定格）；
橙实底节点：正在出队处理，全屏唯一；它的上一拍"处理中"节点此时转绿；
绿实底节点：已处理完毕，终身不褪；
金边：查边拍点亮的活跃边——发现成立就定留金色，这 7 条金边就是 BFS 树（每个节点被发现时走的那条边）；
红闪边：拒绝拍——通向"已在队"节点的边，第二次到达被拒之门外；
距离小字：节点下方 ? → d=0…d=3，发现的瞬间落位、终身不变；"dist = 波纹圈数"就是 BFS 的算术核心；
队列条：字母 token 飞入队尾、从队头滑出，余队左移补位——队里排的就是下一层；
终幕：最短路 S–A–D–G 逐边点亮亮金、四点打 ✓；H–I 保持默认色 + ?——"到不了"本身也是 BFS 的答案。

注意同一条无向边会被两端各检查一次：B–D 在第 9/14 拍、E–G 在第 17/20 拍各来一回——这正是"无向边 = 两条有向边"的具象。

复杂度分析

项目	复杂度	说明
时间	O(V + E)	每个节点入队/出队至多一次，每条无向边至多被两端各检查一次
空间	O(V)	队列 + visited/distance 标记（本动画队列峰值只占到 3 槽）
稳定性	—	遍历类算法无稳定性概念；同层节点的访问次序取决于邻接表顺序（本动画按字母序）

C++ 参考代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 广度优先搜索：无权图单源最短路径
// adj: 邻接表，s: 源点；dist 返回各点到源的最少步数，不可达为 -1
vector<int> bfs(const vector<vector<int>>& adj, int s) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;

    dist[s] = 0;                 // 源点距离 0
    q.push(s);                   // 入队
    while (!q.empty()) {
        int u = q.front();
        q.pop();                 // 出队：先发现的先处理
        for (int v : adj[u]) {   // 逐条检查邻边
            if (dist[v] != -1) continue;  // 已发现（在队或已处理）：拒绝
            dist[v] = dist[u] + 1;        // 首次到达即最少步数
            q.push(v);                    // 入队，进入下一层
        }
    }
    return dist;                 // 到不了的点保持 -1
}

int main() {
    // 与动画相同的图：S A B C D E F G H I = 0..9
    vector<vector<int>> adj = {
        {1, 2},          // S
        {3, 4, 0},       // A
        {4, 5, 0},       // B
        {1, 6},          // C
        {1, 2, 7},       // D
        {2, 7},          // E
        {3},             // F
        {4, 5},          // G
        {9},             // H
        {8},             // I
    };
    for (int d : bfs(adj, 0)) cout << d << ' ';  // 输出：0 1 1 2 2 2 3 3 -1 -1
    cout << endl;
    return 0;
}

什么时候用广度优先搜索

BFS 是"最少步数"三个字的标准答案：无权图（或所有边等价）最短路、迷宫/棋盘最少走步、社交网络最多二度好友、Word Ladder 一次变一个字母、Web 爬虫的广度抓取——凡是最短/最少/最近一层，先想 BFS。它也是一大批图算法的地基：Dijkstra 是带优先队列的 BFS、拓扑排序是入度版 BFS、连通块标记就是从每个未访问点跑一遍 BFS。实现上最易错的两处——"入队时标记 visited（出队才标会重复入队爆队列）"和"邻居已发现的边直接跳过"——正是本动画的入队拍与红闪拒绝拍。