深入理解C++广度优先搜索（BFS）

BFS 与队列（Queue）

BFS 的实现依赖于队列（FIFO，先进先出）这种数据结构。每当我们访问一个节点时，就将其未访问过的邻居加入队列尾部；然后从队列头部取出下一个要访问的节点。这样就能保证按照“由近到远”的顺序遍历。

C++ 实现 BFS 的完整示例

下面是一个使用邻接表表示图，并用 C++ 实现 BFS 的完整代码：

#include <iostream>#include <vector>#include <queue>#include <cstring>using namespace std;// 图的邻接表表示void bfs(int start, const vector<vector<int>>& graph) {    int n = graph.size();    vector<bool> visited(n, false);    queue<int> q;    // 将起始节点入队并标记为已访问    q.push(start);    visited[start] = true;    cout << "BFS 遍历顺序: ";    while (!q.empty()) {        int current = q.front();        q.pop();        cout << current << " ";        // 遍历当前节点的所有邻居        for (int neighbor : graph[current]) {            if (!visited[neighbor]) {                visited[neighbor] = true;                q.push(neighbor);            }        }    }    cout << endl;}int main() {    // 构建一个简单的无向图（邻接表）    // 节点 0 连接 1 和 2；节点 1 连接 0 和 3；等等    vector<vector<int>> graph = {        {1, 2},     // 0        {0, 3},     // 1        {0, 4},     // 2        {1},        // 3        {2}         // 4    };    bfs(0, graph); // 从节点 0 开始 BFS    return 0;}  

代码解析

• graph 是一个 vector<vector<int>>，表示每个节点的邻居列表。
• visited 数组用于记录哪些节点已经被访问过，避免重复访问和死循环。
• 我们使用 STL 中的 queue 来管理待访问的节点。
• 主函数中构建了一个包含 5 个节点的小图，调用 bfs(0, graph) 从节点 0 开始遍历。

BFS 的应用场景

掌握 C++图遍历中的 BFS 算法后，你可以解决许多实际问题，例如：

• 在迷宫中寻找最短路径（假设每步代价相同）
• 社交网络中查找“六度分隔”关系
• 网页爬虫按层级抓取网页
• 检测图是否为二分图（需结合着色）

总结

通过本教程，你应该已经理解了 BFS算法实现的基本原理，并能在 C++ 中编写自己的 BFS 程序。记住，BFS 的关键是“队列 + 标记已访问”。多加练习，你就能轻松应对各种需要图遍历的编程问题。

如果你是算法新手，建议动手运行上面的代码，并尝试修改图的结构或起始节点，观察输出结果的变化。实践是最好的老师！

关键词回顾：C++广度优先搜索、BFS算法实现、C++图遍历、新手BFS教程