广度优先搜索从起始节点开始逐层遍历，使用队列实现并用布尔数组标记访问状态，避免重复访问。示例代码展示了无向图的邻接表表示及BFS遍历过程，输出结果为0 1 2 3 4 5；通过记录队列大小可分层输出，应用于最短路径、连通性等问题，时间与空间复杂度均为O(V + E)。
广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图或树的算法。它从起始节点开始，先访问其所有邻接节点，再逐层向外扩展，直到遍历完所有可达节点。BFS通常使用队列（queue）来实现，保证按层次顺序访问节点。
图的表示方式
在C++中，图常用邻接表表示，可以用vector
示例：无向图的邻接表表示
vector<vector<int>> graph = {
{1, 2}, // 节点0连接1和2
{0, 3, 4}, // 节点1连接0、3、4
{0, 5}, // 节点2连接0、5
{1}, // 节点3连接1
{1}, // 节点4连接1
{2} // 节点5连接2
};BFS基本实现步骤
BFS的核心是使用队列维护待访问节点，并用布尔数组记录已访问状态，避免重复访问。
立即学习“C++免费学习笔记（深入）”；
实现要点：
- 使用queue
保存待处理节点 - 使用vector
标记是否访问过 - 从起点入队，循环出队并处理其邻居
- 未访问的邻居入队并标记
C++代码实现
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(const vector<vector<int>>& graph, int start) {
int n = graph.size();
vector<bool> visited(n, false); // 标记访问状态
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);
}
}
}
}
// 示例调用
int main() {
vector<vector<int>> graph = {{1,2}, {0,3,4}, {0,5}, {1}, {1}, {2}};
cout << "BFS traversal: ";
bfs(graph, 0);
return 0;
}输出结果：
0 1 2 3 4 5
带层级信息的BFS
有时需要知道每个节点所在的层次（距离起点的步数），可以在遍历时记录层数。
修改版：输出每层节点
void bfsWithLevel(const vector<vector<int>>& graph, int start) {
int n = graph.size();
vector<bool> visited(n, false);
queue<int> q;
q.push(start);
visited[start] = true;
int level = 0;
while (!q.empty()) {
int size = q.size(); // 当前层的节点数
cout << "Level " << level << ": ";
while (size--) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
cout << endl;
level++;
}
}输出示例：
Level 0: 0 Level 1: 1 2 Level 2: 3 4 5
应用场景与注意事项
BFS常用于求解最短路径（无权图）、连通分量、拓扑排序等问题。
常见用途：
- 计算两个节点间的最短路径（边权为1）
- 判断图是否连通
- 解决迷宫最短路径问题
- 社交网络中查找好友关系层数
注意点：
- 确保图不为空，起始节点有效
- 无向图需防止来回访问（靠visited数组控制）
- 有向图同样适用，只需按邻接表方向遍历
- 空间复杂度O(V + E)，时间复杂度O(V + E)
基本上就这些。掌握队列的使用和访问标记是关键。
