目录
现在我们已经知道如何用邻接表或邻接矩阵在计算机里“搭建”一个图了。接下来，最基本的操作就是遍历 (Traversal) 这个图——也就是，如何系统性地访问图中的每一个顶点，确保每个顶点只被访问一次。
今天，我们就来学习第一种遍历方法：广度优先搜索 (Breadth-First Search, BFS)。
BFS的诞生——“一石激起千层浪”
想象一下，你站在一个巨大的迷宫的入口，这个迷宫有很多岔路口（顶点）和通道（边）。你的任务是系统地探索整个迷宫。你怎么做？
📍一个非常自然的想法是：
先看看你身边（距离为1步）的所有路口。
然后，再去探索离你2步远的所有路口。
接着，是离你3步远的所有路口。
...以此类推。
这种“由近及远”、“一层一层向外”的探索策略，就像往平静的湖水中扔下一颗石子，波纹会从中心开始，一圈一圈地向外扩散。
图1️⃣：波纹扩散的直观感受
(起点)
/ | \
(1)---(2)---(3) <-- 第一圈波纹 (距离为1)
/ | / | \ | \
(4)(5) (6)(7)(8)(9)(10) <-- 第二圈波纹 (距离为2)
... <-- 第三圈波纹 ...这种探索方式，在图论中，就叫做 广度优先搜索 (BFS)。“广度”或“宽度”指的就是它优先向“水平方向”扩展，探索完一整层之后，才会进入下一层。
BFS的核心机制——如何实现“一层一层”？
我们有了“一层层”探索的思路，但计算机怎么实现这个策略呢？我们需要解决两个关键问题：
记录访问：如何确保一个顶点不会被重复访问，避免在有环的图中陷入死循环？
保证顺序：当我们访问完第一层的所有顶点后，如何能准确地、按顺序地去访问第二层的所有顶点？
✅问题1的解决：标记法
这个问题比较简单。我们可以用一个辅助的布尔数组 visited，大小和顶点数量相同。
visited[i] 为 true 表示顶点 i 已经被访问过，为 false 表示还没有。每次访问一个新顶点前，先检查它的 visited 状态。
✅问题2的解决：一个“待办事项”列表
这是BFS算法的精髓。想象一下，你站在起点 S。
你访问了
S。S的邻居有A,B,C。这些是你下一步要去探索的地方，也就是你的“待办事项”。你应该先把
A,B,C都探索完，才能轮到它们的邻居。所以，你需要一个列表来存放它们：[A, B, C]。现在，你从列表里 最先放进去的
A开始，访问A的邻居，比如D和E。你把D和E也加到“待办事项”列表的 末尾。列表现在是[B, C, D, E]。接下来，你又从列表的 头部 取出
B，访问B的邻居...
我们发现，这个“待办事项”列表有一个鲜明的特点：
先放进去的，先被取出来处理 (First-In, First-Out)。这不就是 队列 (Queue) 的定义吗！
所以，队列 就是实现广度优先搜索“一层一层”特性的核心数据结构。
BFS算法流程图解
我们用一个具体的图来完整地走一遍BFS的流程。
图2️⃣：用于BFS演示的图
(A) --------- (B)
| /
| /
| /
(D) (C) --------- (E)
| /
| /
'--------- (F)我们用邻接表来表示它，并从顶点 A 开始遍历。
准备工作:
visited数组:
[A:F, B:F, C:F, D:F, E:F, F:F](F代表False)队列 (Queue):
[](空的)
第0步: 初始化
选择起始顶点
A。访问
A(比如打印出来)，并标记visited[A] = T。将
A入队。
状态:
访问顺序:
Avisited:
[A:T, B:F, C:F, D:F, E:F, F:F]Queue:
[ A ]
第1步: 处理 A
A出队。找到
A的所有未被访问的邻居：B和D。访问
B和D，标记visited为T，并将它们依次入队。
状态:
访问顺序:
A, B, Dvisited:
[A:T, B:T, C:F, D:T, E:F, F:F]Queue:
[ B, D ](A出队，B和D入队)
第2步: 处理 B
B出队。找到
B的所有未被访问的邻居：C(因为A已经被访问过了)。访问
C，标记visited[C] = T，将C入队。
状态:
访问顺序:
A, B, D, Cvisited:
[A:T, B:T, C:T, D:T, E:F, F:F]Queue:
[ D, C ](B出队，C入队)
第3步: 处理 D
D出队。找到
D的所有未被访问的邻居：没有 (因为A已经被访问过了)。无新顶点入队。
状态:
访问顺序:
A, B, D, Cvisited:
[A:T, B:T, C:T, D:T, E:F, F:F]Queue:
[ C ](D出队)
第4步: 处理 C
C出队。找到
C的所有未被访问的邻居：E和F(因为B已经被访问过了)。访问
E和F，标记visited为T，并将它们依次入队。
状态:
访问顺序:
A, B, D, C, E, Fvisited:
[A:T, B:T, C:T, D:T, E:T, F:T]Queue:
[ E, F ](C出队，E和F入队)
第5、6步: 处理 E 和 F
E出队，它没有未被访问的邻居。F出队，它也没有未被访问的邻居。
最终状态:
访问顺序:
A, B, D, C, E, Fvisited:
[A:T, B:T, C:T, D:T, E:T, F:T]Queue:
[](队列为空)
队列为空，遍历结束。最终的访问顺序为 A -> B -> D -> C -> E -> F。
你可以看到，A (第0层) -> B, D (第1层) -> C (第2层, B的邻居) -> E, F (第3层, C的邻居)，完美地体现了“一层一层”的特性。
C/C++代码实现
我们首先需要自己实现一个简单的队列。这里我们用数组实现一个循环队列。
前提：实现我们自己的队列
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
// 队列结构体
typedef struct {
int data[MAX_QUEUE_SIZE];
int front; // 队头指针
int rear; // 队尾指针
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->front == q->rear;
}
// 入队
void enqueue(Queue *q, int item) {
// 这里简单处理，不考虑队列满的情况
q->data[q->rear] = item;
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE; // 循环队列的关键
}
// 出队
int dequeue(Queue *q) {
int item = q->data[q->front];
q->front = (q->front + 1) % MAX_QUEUE_SIZE; // 循环队列的关键
return item;
}有了这个队列作为工具，我们就可以开始写BFS的代码了。我们假设图是用上一节的 邻接表 实现的。
第一步: BFS函数框架
我们需要一个函数，它接收一个图和一个起始顶点作为参数。在函数内部，我们需要 visited 数组和我们刚刚实现的 Queue。
// 假设 MAX_VERTICES 和 AdjListGraph 结构体已经定义好了
// (从上一节的邻接表代码中获取)
// 对图g从顶点v开始进行一次广度优先搜索
void BFS(AdjListGraph *g, int v) {
int visited[MAX_VERTICES];
for (int i = 0; i < g->num_vertices; i++) {
visited[i] = 0; // 0 表示未访问
}
Queue q;
initQueue(&q);
// ... 算法核心逻辑将在这里填充 ...
}第二步: 处理起始顶点
算法从起始点开始，所以我们需要先访问它，并将其入队。
void BFS(AdjListGraph *g, int v) {
// ... visited数组和队列的初始化 ...
printf("访问顶点: %d\n", v); // 访问
visited[v] = 1; // 标记已访问
enqueue(&q, v); // 入队
// ... 接下来是主循环 ...
}第三步: 核心循环
只要队列不为空，就不断地出队，并处理出队顶点的所有邻居。
void BFS(AdjListGraph *g, int v) {
// ... 初始化和处理起始顶点 ...
while (!isEmpty(&q)) {
int u = dequeue(&q); // 出队一个顶点u
// 遍历u的所有邻居
EdgeNode *p = g->adj_list[u].first_edge; // 拿到u的邻接链表头指针
while (p != NULL) {
// ... 对每个邻居进行处理 ...
p = p->next; // 移到下一个邻居
}
}
}第四步: 完善循环内部逻辑
在遍历邻居的 while 循环中，我们需要判断每个邻居 w 是否已经被访问过。如果没有，就访问它、标记它、并让它入队。
void BFS(AdjListGraph *g, int v) {
// ... 初始化和处理起始顶点 ...
while (!isEmpty(&q)) {
int u = dequeue(&q);
EdgeNode *p = g->adj_list[u].first_edge;
while (p != NULL) {
int w = p->neighbor_index; // 拿到邻居的编号w
// 如果w没有被访问过
if (!visited[w]) {
printf("访问顶点: %d\n", w); // 访问w
visited[w] = 1; // 标记w
enqueue(&q, w); // w入队
}
p = p->next;
}
}
}到这里，从单个连通分量出发的BFS就完成了！
第五步: 处理非连通图
如果图不是连通的，从一个顶点开始的BFS无法访问到所有顶点。所以我们需要一个封装函数来确保所有顶点都被访问到。
void BFSTraverse(AdjListGraph *g) {
int visited[MAX_VERTICES];
for (int i = 0; i < g->num_vertices; i++) {
visited[i] = 0; // 初始化所有顶点为未访问
}
Queue q;
initQueue(&q);
// 遍历每一个顶点
for (int i = 0; i < g->num_vertices; i++) {
// 如果当前顶点还没被访问过，就从它开始进行一次BFS
if (!visited[i]) {
// 这部分逻辑和上面单次BFS几乎一样
printf("访问顶点: %d\n", i);
visited[i] = 1;
enqueue(&q, i);
while (!isEmpty(&q)) {
int u = dequeue(&q);
EdgeNode* p = g->adj_list[u].first_edge;
while (p != NULL) {
int w = p->neighbor_index;
if (!visited[w]) {
printf("访问顶点: %d\n", w);
visited[w] = 1;
enqueue(&q, w);
}
p = p->next;
}
}
}
}
}BFS的应用
BFS绝不只是一个简单的遍历算法，它“一层一层”的特性，让它成为解决某些问题的利器。
求解无权图的最短路径: 从起点
S到终点T的最短路径长度（经过最少的边），就是BFS第一次从S访问到T时所经过的层数。这是因为BFS保证了会先找到所有距离为k的顶点，然后才会去找距离为k+1的顶点。社交网络: 查找“六度空间”理论中的“X度好友”。你的一度好友就是距离为1的邻居，二度好友就是距离为2的顶点，BFS可以轻松帮你找到。
网络爬虫: 在爬取网页时，可以从一个种子URL开始，先爬取所有深度为1的链接，再爬取深度为2的链接，这就是BFS的应用。
掌握了BFS，你就掌握了图论中一个非常强大且基础的工具！