判断C++中两节点是否连通的方法有并查集、DFS和BFS。并查集适用于动态添加边且需频繁查询的场景，通过find和unite操作维护连通分量，查询时比较根节点即可；DFS适合静态图，从起点遍历并标记访问节点，检查目标是否可达；BFS同样用于静态图，利用队列逐层扩展，可同时求最短路径。实际应用中，动态连通性选并查集，静态图则根据需求选DFS或BFS。
在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判断连通性
适用于静态图，一次性构建后进行连通性查询。通过遍历从起点可达的所有节点，检查目标节点是否被访问过。
- 使用邻接表存储图。 - 从起始节点开始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。
