核心思想

BFS（Breadth First Search，广度优先搜索）从一个顶点出发，先访问离它最近的顶点，再逐层向外扩展。

它具有两个特点：

  • 一层一层访问
  • 先发现的顶点先处理

因此，BFS 使用**队列（Queue）**实现。

基本过程

以下图为例：

和二叉树的层级遍历还挺像。

    A
   / \
  B   C
 / \   \
D   E   F

从 A 开始进行 BFS，访问顺序为：

A → B → C → D → E → F

对应的访问层次为：

第 0 层：A
第 1 层：B C
第 2 层：D E F

实现要点

队列

BFS 的基本流程如下：

  1. 将起点标记为已访问并入队。
  2. 取出队首顶点并访问。
  3. 将该顶点所有未访问的邻接点标记并入队。
  4. 重复以上过程，直到队列为空。

visited 数组

visited[i] = true

表示顶点 i 已经被访问过，主要用于：

  • 防止顶点被重复访问
  • 防止在有环图中无限循环

例如：

A — B
|   |
C — D

如果没有 visited，可能不断循环：

A → B → D → C → A → ...

重点：顶点应在入队时标记为已访问，避免同一顶点被多个邻接点重复加入队列。

非连通图

从一个顶点执行一次 BFS，只能访问该顶点所在的连通分量。要遍历整个图，需要在外层依次检查所有顶点：

for (每个顶点 v)
{
    if (!visited[v])
        BFS(G, v);
}

对于无向图，调用 BFS 的次数等于图的连通分量数。

复杂度

设顶点数为 VV，边数为 EE：

存储方式 时间复杂度 原因
邻接表 O(V+E)O(V + E) 每个顶点访问一次，每条边检查有限次
邻接矩阵 O(V2)O(V^2) 对每个顶点都要扫描矩阵的一整行

visited 数组和队列都需要额外空间，因此空间复杂度为 O(V)O(V)。

最短路径性质

对于无权图或所有边权相同的图，BFS 可以求出起点到其他顶点的最短路径长度。

因为 BFS 是逐层搜索：

第 0 层：距离 0
第 1 层：距离 1
第 2 层：距离 2
第 3 层：距离 3

因此，一个顶点第一次被 BFS 访问时，对应的路径就是边数最少的路径。

注意： BFS 一般不能直接解决边权不同的最短路径问题。

常见用途

  • 图的遍历
  • 判断图是否连通
  • 求无权图最短路径
  • 求顶点之间最少经过多少条边
  • 求连通分量
  • 层序扩展问题
  • 树的层序遍历

BFS 与 DFS 对比

BFS DFS
广度优先 深度优先
一层一层搜索 一条路尽量走到底
队列 栈 / 递归
适合无权最短路径 适合回溯、连通性等
空间可能较大 搜索深度可能较大

代码

代码部分与树的层序遍历几乎一样，但需要注意使用 visited 数组。

// 邻接表方式
void BFS(const ALGraph& G, const int start) {
    bool visited[MAXV] = {false};

    std::queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        std::cout << u << " ";

        ArcNode* p = G.vertices[u].first;

        while (p != nullptr) {
            int v = p->adjvex;

            if (!visited[v]) {
                q.push(v);
                visited[v] = true;
            }

            p = p->next;
        }
    }
}

总结

  • 核心数据结构：队列
  • 标记时机：顶点入队时
  • 邻接表时间复杂度：O(V+E)O(V + E)
  • 邻接矩阵时间复杂度：O(V2)O(V^2)
  • 空间复杂度：O(V)O(V)
  • 核心优势：求无权图的最短路径
  • 遍历非连通图：在 BFS 外层再遍历所有顶点

其实我还没有看网课，
今天早上把代码梳理消化了一遍，
明天再去把知识点记一记，顺便继续DFS。

今天的学习任务完成的还算比较快，不到19：00就结束了。
不过数学进度还是慢啊，怎么感觉题目这么多新知识。 有点麻烦。 ╮(╯▽╰)╭
海边的贵贵