C++图的BFS遍历
较难2图的广度优先搜索：像水波一样一圈圈探索
想象一下，你把一颗石子扔进平静的湖面，水面会泛起一圈一圈的波纹，从中心向外扩散。广度优先搜索（BFS） 就像这种波纹——它从一个起点出发，先访问离起点最近的邻居，再访问邻居的邻居，一层一层向外探索。在计算机里，BFS常用来解决“最短路径”“连通性”等问题，比如在迷宫游戏里找到从起点到终点的最短路线，或者在社交网络中找出你和某个朋友之间最少通过几个人认识。
1. BFS的核心思想：先近后远
BFS的规则很简单：先访问离起点距离为1的所有顶点，再访问距离为2的，然后是距离为3的……
举个例子：假设你是一个班长，要在班级里快速传递一个通知。你先把通知告诉坐在你周围的4个同学（距离为1），然后这4个同学再告诉他们周围的同学（距离为2），这样消息就像波纹一样扩散开。BFS保证每个节点第一次被访问时，就是从起点到它的最短路径（在无权图中）。
- 生活中的例子：老师让小明把作业传给全班同学，但不能重复传。小明先把作业递给前后左右的同学，这些同学再递给他们周围还没拿到作业的人。这样每次传递，作业离小明就更远一层，这就是BFS。
2. 用队列实现“一层一层”的访问
BFS需要一个关键工具：队列（Queue）。队列的特点是“先进先出”，就像排队买零食——先排的人先买到。在BFS中，我们先把起点加入队列，然后重复以下步骤：
- 从队列取出一个顶点（排在最前面的）。
- 访问这个顶点（比如打印它的编号）。
- 把这个顶点的所有未访问的邻居加入队列（排在队尾）。
这样，队列里永远先存放“当前层”的顶点，再存放“下一层”的顶点。因为队列先进先出，所以当前层的顶点会先被取出并访问，之后才是下一层。
对比生活中的排队：想象你在游乐场排队玩过山车， BFS就相当于让一个项目的工作人员先服务完当前排队的游客，然后再叫下一批游客进入。而DFS（深度优先搜索）就像一个人发现一个好玩的项目就一口气玩到底，再回来玩别的。
3. 代码实现：一步一步拆解
我们还是用邻接表来存储图（每个顶点用数组存它的邻居列表）。需要一个 visited 数组记录哪些顶点已经被访问过，防止重复入队。
下面这段代码实现了从起点0开始的BFS遍历：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> graph[MAXN]; // 邻接表，graph[i]里存着i的所有邻居编号
bool visited[MAXN]; // 标记是否访问过
void bfs(int start) {
queue<int> q; // 创建一个队列，用来存待访问的顶点
q.push(start); // 把起点放进队列
visited[start] = true; // 标记起点已访问
while (!q.empty()) {
int u = q.front(); // 取出队首顶点（当前要访问的顶点）
q.pop(); // 把它从队列里删掉
cout << u << " "; // 访问这个顶点（打印编号）
// 遍历u的所有邻居
for (int v : graph[u]) {
if (!visited[v]) { // 如果邻居还没访问过
visited[v] = true; // 标记为已访问（防止重复）
q.push(v); // 邻居入队，等到下一层再访问
}
}
}
}
代码关键点：
- 每次从队列取出一个顶点，立即访问它。
- 遍历它的邻居时，只有未访问过的邻居才入队，并且要立刻标记为已访问。为什么要立刻标记？因为如果不标记，同一个邻居可能被多个上层顶点重复加入队列，导致死循环（比如两个顶点互相连接）。
4. 完整的可运行示例：一个具体图
让我们用一个小图来测试。图中有5个顶点（编号0到4），边为：0-1, 0-2, 1-3, 1-4（无向图）。从顶点0开始BFS。
int main() {
int n = 5; // 顶点数
int m = 4; // 边数
// 手动加边，也可以用循环输入
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(0);
graph[1].push_back(3);
graph[1].push_back(4);
graph[2].push_back(0);
graph[3].push_back(1);
graph[4].push_back(1);
bfs(0); // 从顶点0开始遍历
return 0;
}
运行结果：0 1 2 3 4
过程解释：
- 第一层（距离0）：起点0。访问0，把它的邻居1和2入队。队列：[1, 2]
- 第二层（距离1）：取出1，访问1，把它的未访问邻居3和4入队。队列：[2, 3, 4]
- 取出2，访问2（它只有邻居0，但0已访问，无新邻居）。队列：[3, 4]
- 第三层（距离2）：取出3，访问3；取出4，访问4。队列空。 输出顺序正好是先距离1的（1和2），再距离2的（3和4）。
5. 常见错误（新手要小心）
- 忘记标记
visited：如果只入队不标记，同一个顶点可能被多次加入队列，程序会无限循环（因为每次从队列取出又会把它的邻居再入队）。一定要在入队时立即标记，而不是在访问时标记（虽然访问时标记也可以，但入队时标记可以防止重复入队，更高效）。 - 邻接表只加一边：对于无向图，边
u-v需要在graph[u]和graph[v]中都加入，否则遍历时只能单向走。如果忘记加另一侧，会导致部分顶点无法到达。 - 队列使用错误：注意
q.front()只返回队首元素，要用q.pop()删除它。忘记pop会导致死循环。 - 起点未标记：
bfs函数开头一定要把起点标记为已访问，否则起点自己可能被重复加入队列。
6. BFS和DFS的对比：一个水平，一个垂直
| 特点 | BFS（广度优先） | DFS（深度优先） |
|---|---|---|
| 数据结构 | 队列 | 栈（或递归） |
| 访问顺序 | 一层一层，先近后远 | 一条路走到底，再回溯 |
| 适用场景 | 最短路径（无权图）、连通性 | 拓扑排序、路径查找、连通块 |
| 记忆辅助 | 像水波扩散 | 像钻头往下钻 |
举个例子：如果你在迷宫里找出口，BFS保证第一次找到出口时走的是最短路径；DFS则可能先钻进一条死胡同，绕很远才能找到出口。
7. 完整可运行的代码（包含输入）
下面是一个完整的程序，可以从键盘输入顶点数和边数，然后输入所有边，最后从顶点0开始BFS遍历。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> graph[MAXN]; // 邻接表
bool visited[MAXN]; // 访问标记
void bfs(int start) {
queue<int> q; // 队列
q.push(start); // 起点入队
visited[start] = true; // 标记起点
while (!q.empty()) {
int u = q.front(); // 取出队首
q.pop();
cout << u << " "; // 访问当前顶点
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v); // 未访问的邻居入队
}
}
}
}
int main() {
int n, m; // n个顶点，m条边
cout << "请输入顶点数和边数：";
cin >> n >> m;
cout << "请输入每条边的两个顶点（编号从0开始）：" << endl;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v); // 无向图，加边两次
graph[v].push_back(u);
}
cout << "BFS遍历结果（从顶点0开始）：";
bfs(0);
cout << endl;
return 0;
}
运行示例：
请输入顶点数和边数：5 4
请输入每条边的两个顶点（编号从0开始）：
0 1
0 2
1 3
1 4
BFS遍历结果（从顶点0开始）：0 1 2 3 4
8. 学完BFS后，可以继续学习什么？
- 用BFS求最短路径：记录每个顶点是从哪个顶点过来的（父节点），遍历结束后反向输出路径。
- BFS与队列的更多应用：比如在树中做层序遍历，在网格中做“洪水填充”算法（类似“扫雷”游戏自动展开空白区域）。
- DFS（深度优先搜索）：用栈或递归实现，适合解决“全排列”“八皇后”等问题。
- 图的存储方式：邻接矩阵 vs 邻接表，了解不同数据结构的优缺点。
- 拓扑排序：利用队列的BFS思想可以解决课程安排等依赖关系问题。
BFS是你掌握图算法的一把钥匙，理解它之后，很多看似复杂的问题都能用“一层一层扩散”的思路来解决。试着写一个小程序，用BFS找到从你家到学校的地图最短路线吧！
例题精讲
在C++中实现图的BFS遍历时，通常使用哪种数据结构来管理待访问的顶点？
对于任意有向图，从某个源点出发进行BFS遍历，一定能访问到图中所有顶点。
以下BFS代码中，访问顶点u后，遍历邻接顶点v，若v未访问则标记并加入队列。请补充空缺语句：
for(int v : adj[u]){
if(!visited[v]){
visited[v]=true;
___;
}
}