广度优先搜索 c++

以下是C++中实现广度优先搜索算法的示例代码：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 定义图的邻接表表示
class Graph {
private:
    int V; // 图中顶点的数量
    vector<vector<int>> adj; // 邻接表

public:
    Graph(int v) {
        V = v;
        adj.resize(V);
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    // 广度优先搜索算法
    void BFS(int start) {
        vector<bool> visited(V, false); // 记录顶点是否被访问过
        queue<int> q; // 用于存储待访问的顶点

        visited[start] = true; // 标记起始顶点为已访问
        q.push(start); // 将起始顶点加入队列

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            cout << curr << " "; // 输出当前访问的顶点

            // 遍历当前顶点的所有邻接顶点
            for (int i = 0; i < adj[curr].size(); i++) {
                int neighbor = adj[curr][i];
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // 标记邻接顶点为已访问
                    q.push(neighbor); // 将邻接顶点加入队列
                }
            }
        }
    }
};

int main() {
    // 创建一个有向图
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);

    cout << "广度优先搜索结果: ";
    g.BFS(0); // 从顶点0开始进行广度优先搜索

    return 0;
}

该示例代码实现了一个有向图的广度优先搜索算法。首先，我们定义了一个`Graph`类来表示图的邻接表。然后，我们使用`addEdge`方法添加图的边。最后，我们使用`BFS`方法来执行广度优先搜索算法，并从指定的起始顶点开始遍历图。