广度优先搜索（BFS）是一种按层遍历图的算法，使用队列实现并维护访问标记，适用于最短路径与连通性问题。从起始节点开始，依次将未访问的邻接节点入队，直至队列为空。C++中常用vector数组构建邻接表存储图结构，并通过bool数组记录节点访问状态。核心步骤包括：起始节点入队并标记、循环处理队首节点及其邻接点，直到队列为空。示例程序构建含6个节点的无向图，调用BFS后输出结果为1 2 3 4 5 6，体现了逐层扩展的遍历顺序。该算法结构清晰，关键在于队列调度与状态控制。
广度优先搜索（BFS）是图论中一种基础的遍历算法，适用于求解最短路径、连通性等问题。在C++中，BFS通常借助队列（queue）实现，保证按层访问节点。
基本思路
BFS从起始节点开始，先访问其所有邻接节点，再逐层向外扩展。使用一个队列保存待访问的节点，同时用一个数组或集合记录已访问的节点，避免重复处理。
关键步骤：- 将起始节点入队，并标记为已访问
- 当队列非空时，取出队首节点
- 访问该节点的所有未访问邻接节点，依次入队并标记
- 重复直到队列为空
图的表示方式
常用邻接表存储图，C++中可用vector的数组或vector的vector实现。
示例：无向图的邻接表表示
立即学习“C++免费学习笔记（深入）”；
const int MAXN = 1e5 + 5; vectorgraph[MAXN]; // 邻接表 bool visited[MAXN]; // 访问标记数组
BFS核心代码实现
使用STL中的queue完成节点调度。
void bfs(int start) {
queue 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);
}
}
}
}
完整示例：图的BFS遍历
构建一个包含6个节点的无向图并执行BFS。
#include#include #include using namespace std; const int MAXN = 7; vector graph[MAXN]; bool visited[MAXN]; void addEdge(int u, int v) { graph[u].push_back(v); graph[v].push_back(u); } void bfs(int start) { queue 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() { addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(3, 6); bfs(1); // 输出: 1 2 3 4 5 6 return 0; }
基本上就这些。BFS的核心在于队列的使用和访问状态的维护，结构清晰，适合解决分层遍历问题。
