c++邻接表实现广度优先遍历的代码

在 C++ 中，使用邻接表（Adjacency List）数据结构来实现广度优先搜索（BFS）通常涉及以下几个步骤：

首先，你需要定义一个顶点类 `Vertex` 和一个边的表示类，比如 `Edge`，它们可以包含顶点和权重信息。

class Vertex {
public:
    int id;
    std::vector<Edge> neighbors; // 邻居列表
};

class Edge {
public:
    int destination;
    // 其他可能需要的数据如权重等
};

然后，你可以创建一个队列来保存当前层的节点，并初始化它，同时设置起点作为已访问集合的一部分。

std::queue<Vertex*> queue;
std::set<int> visited;

void bfs(Vertex* start) {
    queue.push(start);
    visited.insert(start->id);
    
    while (!queue.empty()) {
        Vertex* current = queue.front();
        queue.pop();

        // 输出当前节点的信息
        std::cout << "Visiting vertex: " << current->id << "\n";

        // 遍历邻居并加入队列，如果邻居未访问过
        for (const auto& neighbor : current->neighbors) {
            if (visited.find(neighbor.destination) == visited.end()) {
                visited.insert(neighbor.destination);
                queue.push(&neighbor.destination);
            }
        }
    }
}

要在主函数中调用这个函数，只需要传入起始节点即可：

int main() {
    Vertex v1{1, {}};
    Vertex v2{2, {v1, /* other edges... */}};
    // 更多顶点...

    bfs(&v1); // 从v1开始做BFS

    return 0;
}