c++中如何判断两个节点是否连通_c++节点连通性判断方法-C++-PHP中文网

c++中如何判断两个节点是否连通_c++节点连通性判断方法

穿越時空

发布： 2025-09-30 09:56:02

原创

376人浏览过

判断C++中两节点是否连通的方法有并查集、DFS和BFS。并查集适用于动态添加边且需频繁查询的场景，通过find和unite操作维护连通分量，查询时比较根节点即可；DFS适合静态图，从起点遍历并标记访问节点，检查目标是否可达；BFS同样用于静态图，利用队列逐层扩展，可同时求最短路径。实际应用中，动态连通性选并查集，静态图则根据需求选DFS或BFS。

c++中如何判断两个节点是否连通_c++节点连通性判断方法

在C++中判断两个节点是否连通，通常出现在图结构的应用场景中。常见的方法包括使用并查集（Union-Find）、深度优先搜索（DFS）或广度优先搜索（BFS）。具体选择哪种方式，取决于图的存储形式以及操作频率。

使用并查集判断连通性

并查集适合频繁查询和动态添加边的场景，能高效判断两个节点是否属于同一个连通分量。

- 初始化每个节点的父节点为自己。 - 合并操作（union）将两个节点所在集合合并。 - 查询操作（find）判断两个节点的根节点是否相同。

示例代码：

#include <vector>
using namespace std;
<p>struct UnionFind {
vector<int> parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}</p><pre class='brush:php;toolbar:false;'>int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]); // 路径压缩
    return parent[x];
}

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

bool connected(int x, int y) {
    return find(x) == find(y);
}

登录后复制

};

调用 connected(x, y) 即可判断两节点是否连通。

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

使用DFS判断连通性

适用于静态图，一次性构建后进行连通性查询。通过遍历从起点可达的所有节点，检查目标节点是否被访问过。

通义万相

通义万相，一个不断进化的AI艺术创作大模型

596

查看详情

- 使用邻接表存储图。 - 从起始节点开始DFS，标记访问过的节点。 - 检查目标节点是否在本次遍历中被访问。

示例代码片段：

bool dfs(int u, int target, vector<bool>& target visited, const vector<vector<int>>& adj) {
    if (u == target) return true;
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v] && dfs(v, target, visited, adj))
            return true;
    }
    return false;
}
<p>// 调用前需初始化visited数组
vector<bool> visited(n, false);
bool is_connected = dfs(start, end, visited, adj);

登录后复制

使用BFS判断连通性

BFS与DFS逻辑类似，只是使用队列逐层扩展，适合求最短路径的同时判断连通。

- 初始化队列并将起点入队。 - 逐层访问邻居节点，直到找到目标或遍历完成。 - 若过程中访问到目标节点，则连通。

示例代码片段：

#include <queue>
bool bfs(int start, int target, const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(start);
    visited[start] = true;
<pre class='brush:php;toolbar:false;'>while (!q.empty()) {
    int u = q.front(); q.pop();
    if (u == target) return true;

    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}
return false;

登录后复制

}

基本上就这些常见方法。根据实际需求选择合适的方式：动态连通性用并查集，静态图可用DFS或BFS。

以上就是c++++中如何判断两个节点是否连通_c++节点连通性判断方法的详细内容，更多请关注php中文网其它相关文章！