C++ 广度优先遍历

在C++中，广度优先遍历(Breadth-First Search, BFS)是一种用于图或树的数据结构搜索算法。它的基本思想是从起点开始，按照节点间的邻接关系逐层探索，直到找到目标节点或者遍历完整个图。BFS通常用于寻找最短路径、连通分量等问题。

下面是一个简单的BFS遍历的步骤：

1. 创建一个队列，并将起始节点放入队列中。
2. 当队列非空时，从队列头部取出一个节点，称为当前节点。
3. 对当前节点进行处理（例如访问、标记等），然后将其所有未访问过的邻居加入到队列的尾部。
4. 重复步骤2和3，直到队列为空。

C++中，可以使用`std::queue`容器配合迭代器来实现这一过程。如果需要保存遍历路径，还可以添加一个额外的数据结构（如栈或列表）记录每个节点的前驱。

以下是一个使用`std::queue`的基本模板：

#include <iostream>
#include <queue>
using namespace std;

void bfs(const vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int curr = q.front();
        cout << curr << " ";

        for (int neighbor : graph[curr]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }

        q.pop();
    }
}

int main() {
    vector<vector<int>> graph = {{0, 1, 2},
                                  {1, 0, 3},
                                  {2, 3, 0}};
    bfs(graph, 0); // 输出 0 1 2 3
    return 0;
}