c++中如何判断图是否连通_c++图连通性判断方法

判断图是否连通可通过DFS、BFS或并查集实现：1）DFS从顶点0出发遍历，访问数等于总顶点数则连通；2）BFS同理，用队列逐层扩展；3）并查集将边两端合并，最后所有顶点根相同则连通。

在C++中判断图是否连通，主要针对无向图进行操作。如果图中任意两个顶点之间都存在路径，则称该图为连通图。以下是常用的几种判断方法。

使用深度优先搜索（DFS）

从任意一个顶点出发，使用DFS遍历图，记录访问过的节点数量。若访问的节点数等于图的总顶点数，则图是连通的。

步骤如下：

• 选择一个起始顶点（如0号顶点）
• 调用DFS，标记所有能到达的顶点
• 统计被访问的顶点个数
• 若个数等于总顶点数，图连通；否则不连通

#include 
#include 
using namespace std;

void dfs(int u, vector& visited, const vector>& graph) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v, visited, graph);
        }
    }
}

bool isConnected(const vector>& graph, int n) {
    vector visited(n, false);
    dfs(0, visited, graph);

    for (int i = 0; i < n; i++) {
        if (!visited[i]) return false;
    }
    return true;
}

使用广度优先搜索（BFS）

BFS与DFS思路一致，只是换用队列实现遍历。

GitHub Copilot

GitHub AI编程工具，实时编程建议

下载

立即学习“C++免费学习笔记（深入）”；

将起始点入队，逐层访问其邻居，标记已访问节点。结束后检查是否所有节点都被访问。

bool isConnectedBFS(const vector>& graph, int n) {
    vector visited(n, false);
    queue q;
    q.push(0);
    visited[0] = true;
    int count = 1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
                count++;
            }
        }
    }
    return count == n;
}

使用并查集（Union-Find）

适用于边列表形式的图。通过合并每条边的两个顶点所在集合，最终判断所有顶点是否属于同一个集合。

• 初始化每个顶点为独立集合
• 对每条边执行union操作
• 检查所有顶点是否有相同的根节点

int find(vector& parent, int x) {
    if (parent[x] != x)
        parent[x] = find(parent, parent[x]);
    return parent[x];
}

void unite(vector& parent, int x, int y) {
    int rx = find(parent, x), ry = find(parent, y);
    if (rx != ry)
        parent[rx] = ry;
}

bool isConnectedUnionFind(int n, const vector>& edges) {
    vector parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;

    for (auto& e : edges) {
        unite(parent, e.first, e.second);
    }

    int root = find(parent, 0);
    for (int i = 1; i < n; i++) {
        if (find(parent, i) != root)
            return false;
    }
    return true;
}