Appearance
广度优先搜索（BFS）
为什么需要广度优先搜索
图的遍历是图论算法的基础。与树不同，图中可能存在回路，直接遍历会导致死循环，因此需要专门的遍历策略。
广度优先搜索（Breadth-First Search, BFS）是图的两种基本遍历方式之一。它从某个顶点出发，逐层向外扩展访问所有可达顶点，类似于树的层序遍历。BFS 在求解无权图最短路径、判断连通性等问题中有直接应用，是 408 考研图论章节的核心考点。
核心思想
BFS 的核心特点：
- 逐层访问：先访问起始顶点，再访问其所有邻接顶点，然后访问邻接顶点的邻接顶点，依此类推
- 借助队列：用队列（FIFO）保存已访问但邻接顶点尚未全部访问的顶点，保证层次顺序
- visited 数组：用布尔数组标记每个顶点是否已被访问，防止重复入队
BFS 的过程可以类比"水波扩散"——从一个点投下石子，波纹一圈一圈向外扩展。
层次 0: v₀
层次 1: v₁ v₂ v₃ （v₀ 的邻接顶点）
层次 2: v₄ v₅ （v₁v₂v₃ 的未访问邻接顶点）
...交互可视化
通过下方的交互动画，你可以逐步观察广度优先搜索的执行过程：
操作详解
算法思路
从顶点 v 出发进行 BFS 的步骤：
- 访问起始顶点 v，标记
visited[v] = true，将 v 入队 - 当队列非空时，循环执行：
- 队头顶点 u 出队
- 依次检查 u 的所有邻接顶点 w：若
visited[w] == false，则访问 w，标记visited[w] = true，将 w 入队
- 队列为空时，从 v 出发可达的所有顶点均已访问
对于非连通图，一次 BFS 只能访问一个连通分量。需要遍历所有顶点，对未访问的顶点再次调用 BFS，才能完成整个图的遍历。
邻接矩阵实现
c
#define MAX_VERTEX 100
bool visited[MAX_VERTEX];
int Graph[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵
int n; // 顶点数
void BFS(int v) {
int queue[MAX_VERTEX], front = 0, rear = 0;
printf("%d ", v); // 访问起始顶点
visited[v] = true;
queue[rear++] = v; // 入队
while (front != rear) {
int u = queue[front++]; // 出队
for (int w = 0; w < n; w++) {
if (Graph[u][w] == 1 && !visited[w]) {
printf("%d ", w);
visited[w] = true;
queue[rear++] = w;
}
}
}
}
// 遍历整个图（处理非连通图）
void BFSTraverse() {
for (int i = 0; i < n; i++)
visited[i] = false;
for (int i = 0; i < n; i++) {
if (!visited[i])
BFS(i);
}
}邻接矩阵中，查找顶点 u 的所有邻接顶点需要遍历矩阵的一整行，因此内层循环执行 O(V) 次。
邻接表实现
c
typedef struct ArcNode {
int adjvex; // 邻接顶点编号
struct ArcNode *next;
} ArcNode;
typedef struct {
int data; // 顶点数据
ArcNode *first; // 边链表头指针
} VNode;
VNode AdjList[MAX_VERTEX];
void BFS_AdjList(int v) {
int queue[MAX_VERTEX], front = 0, rear = 0;
printf("%d ", v);
visited[v] = true;
queue[rear++] = v;
while (front != rear) {
int u = queue[front++];
ArcNode *p = AdjList[u].first;
while (p != NULL) {
int w = p->adjvex;
if (!visited[w]) {
printf("%d ", w);
visited[w] = true;
queue[rear++] = w;
}
p = p->next;
}
}
}邻接表中，每个顶点只遍历其边链表，总共访问所有边结点恰好一次（无向图为 2E 次），效率更高。
BFS 生成树
对连通图从顶点 v 进行 BFS 时，所有引起顶点首次被访问的边构成一棵树，称为 BFS 生成树。
BFS 生成树的特点：
- 树的根为起始顶点 v
- 树中从根到任意顶点的路径，就是原图中从 v 到该顶点的最短路径（边数最少）
- 同一张图，邻接矩阵和邻接表的存储方式不同（邻接顶点的遍历顺序不同），生成树可能不同
对于非连通图，每个连通分量各产生一棵 BFS 生成树，合在一起构成 BFS 生成森林。
复杂度分析
| 存储方式 | 时间复杂度 | 说明 |
|---|---|---|
| 邻接表 | O(V + E) | 每个顶点入队一次 O(V)，每条边检查一次 O(E) |
| 邻接矩阵 | O(V²) | 每个顶点入队一次，查找邻接顶点需遍历一整行 |
空间复杂度：O(V)，主要开销为 visited 数组（O(V)）和辅助队列（最坏情况下存储 O(V) 个顶点）。
考研高频考点
- ⭐ 给定图结构，写出 BFS 遍历序列（选择题/填空题高频，注意起始顶点和存储方式影响序列）
- ⭐ BFS 与 DFS 的对比（简答题必考）：BFS 用队列、DFS 用栈（递归）；BFS 适合求最短路径、DFS 适合求路径是否存在
- ⭐ BFS 的时间复杂度：邻接表 O(V+E)，邻接矩阵 O(V²)（选择题常考）
- ⭐ BFS 生成树/森林的概念及性质（树的路径 = 最短路径）
- BFS 判断图的连通性：调用 BFS 的次数 = 连通分量个数
- BFS 求无权图单源最短路径（应用题）