宽度优先搜索c++

宽度优先搜索（BFS）是一种图遍历算法，可以用来解决很多问题，比如最短路径、连通性、拓扑排序等等。以下是一个简单的宽度优先搜索的 C++ 实现：

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

const int MAXN = 100; // 最大节点数
vector<int> adj[MAXN]; // 邻接表
bool vis[MAXN]; // 是否访问过

void bfs(int s) {
    queue<int> Q; // 存放节点的队列
    Q.push(s); // 将起点加入队列
    vis[s] = true; // 标记起点已被访问
    while (!Q.empty()) { // 只要队列不空，就一直搜索
        int x = Q.front(); // 取出队首节点
        Q.pop(); // 弹出队首节点
        for (int i = 0; i < adj[x].size(); i++) { // 枚举与 x 相邻的节点
            int y = adj[x][i];
            if (!vis[y]) { // 如果 y 没有被访问过
                Q.push(y); // 将 y 加入队列
                vis[y] = true; // 标记 y 已被访问
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y; // 输入一条边的两个端点
        adj[x].push_back(y); // 存储邻接表
        adj[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { // 如果 i 没有被访问过
            bfs(i); // 从 i 开始搜索连通块
        }
    }
    return 0;
}

在这个实现中，我们使用邻接表来存储图，使用一个 bool 数组来标记每个节点是否被访问过，使用一个 queue 来存放待搜索的节点。首先，我们从起点开始搜索，将起点加入队列并标记为已访问。然后，只要队列不空，就不断取出队首节点 x 并枚举与 x 相邻的节点 y。如果 y 没有被访问过，我们就将 y 加入队列并标记为已访问。这样，我们就可以搜索出从起点能够到达的所有节点了。如果图不连通，我们需要对每个没有被访问过的节点都进行一次搜索，这样就可以找到所有连通块了。