bfs或dfs可直接判断两顶点是否连通，无需构建完整路径；bfs适合最短路径，dfs递归更简洁；时间复杂度均为o(v+e)，空间上bfs用队列、dfs用栈；有向图需明确路径方向，无向图默认处理；推荐邻接表存储，稀疏图更省空间；多次查询宜用并查集预处理，单次查询接近常数时间；dfs递归过深易栈溢出，可改非递归实现；bfs需防重复入队，数组索引须校验范围。
用 BFS 或 DFS 判断两个顶点是否连通最直接
不需要构建完整路径，只要确认存在任意一条路径即可。BFS 更适合找最短路径（虽然这里不关心长度），DFS 递归写起来更紧凑；两者时间复杂度都是 O(V + E)，空间上 BFS 是队列开销，DFS 是栈深度（最坏 O(V)）。
关键点：图可能不连通、有向/无向、含环，但连通性判断本身不依赖方向性——对有向图，得明确是“是否存在从 u 到 v 的路径”，还是“在无向化意义下是否属于同一连通分量”。默认按无向图处理，若为有向图需额外说明方向。
- 初始化访问数组（
vector<bool> visited(n, false)</bool>），避免重复访问和死循环 - 起点入队/入栈后立即标记
visited[start] = true，否则可能重复加入 - 邻接表推荐用
vector<vector>></vector>，比邻接矩阵省空间，尤其稀疏图 - 若顶点编号不连续（如 ID 是字符串或大整数），改用
unordered_map<int vector>></int>存图
用并查集（Union-Find）做多次查询更高效
如果要反复判断不同顶点对的连通性（比如 1000 次查询），BFS/DFS 每次都重跑太慢。先用一次 O(E α(V)) 时间预处理整个图，之后每次查询仅需 O(α(V))（接近常数）。
注意：并查集只能回答“是否在同一连通分量”，不能给出路径，也不支持删边。动态加边可用，但删边需换 LCT 或其他结构。
- 初始化时对每个顶点调用
make_set()，或构造函数里直接parent[i] = i - 遍历所有边，对每条
(u, v)调用union_sets(u, v) - 查询前确保已执行完所有 union，否则
find_set(u) == find_set(v)结果不准 - 路径压缩 + 按秩合并必须同时启用，否则最坏退化成
O(n)查询
遇到 “segmentation fault” 或 “stack overflow” 怎么办
DFS 递归太深（比如链状图 10⁵ 个节点）会爆栈；BFS 队列过大或未限制访问可能内存溢出；数组越界常见于顶点编号从 1 开始但代码按 0 索引访问。
- DFS 改非递归：手动用
stack<pair int>></pair>存当前节点和邻接索引，避免系统栈溢出 - BFS 加访问检查：每次
pop后立刻验证visited[node]，防止重复入队 - 图输入时校验顶点范围：
if (u = n || v = n)，及时报错 - 用
vector<vector>> graph(n)</vector>初始化邻接表，别漏掉n参数
C++ 实现片段：BFS 判连通（带注释）
bool is_connected(const vector<vector>>& graph, int start, int end, int n) {
if (start == end) return true;
vector<bool> visited(n, false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (v == end) return true;
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
return false;
}
</int></bool></vector>
这段代码假设图是无向的，且顶点编号为 0 到 n-1。如果 end 在遍历中途命中就立刻返回，不必等整个连通分量扫完——这是优化关键。
实际用的时候，别忘了传入正确的 n（顶点总数），也别把 graph 定义成全局变量却在多线程里复用——visited 数组必须每次查询新建。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
