c++ bfs 获取遍历路径

在C++中，BFS（广度优先搜索）通常用于图论中的遍历和查找最短路径，特别是在无权图或有向图的情况下。当你想要获取从起点到终点的遍历路径时，可以按照以下步骤操作：

1. 定义一个队列，用于存储待访问的节点。
2. 将起点加入队列，并将其标记为已访问（例如设置为白色，代表未探索）。
3. 开始循环，只要队列不为空：
a. 弹出队首节点作为当前节点。
b. 输出当前节点，表示它在路径上。
c. 遍历当前节点的所有邻居（邻接节点），如果它们还没有被访问过，则将它们加入队列并标记为已访问（通常是通过颜色变化或标记数组来实现）。
4. 当队列为空且所有邻居都被访问过时，说明已经找到路径；如果没有找到路径，就表示起点和终点之间没有连通。

这里是一个简单的C++伪代码示例：

#include <queue>
using namespace std;

vector<int> graph[vertex_num]; // 图的邻接列表表示
bool visited[vertex_num] = {false}; // 初始化所有节点为未访问

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true; // 标记起点已访问

    while (!q.empty()) {
        int curr = q.front();
        cout << curr << " "; // 输出路径节点
        q.pop();

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