适用读者：会写 BFS/DFS，但遇到"动态加边后判断连通"就卡住的人。
前置：S03-B06。
实测环境：Python 3.12.3（并查集三种实现）；实测日期 2026-11-05。
覆盖旧文：A-1510（图，227 点）、A-1509（并查集，235 点）= 462 点。
覆盖扩展：E-S03-010（拓扑排序与环检测）。
上一篇：S03-B06 · 树家族：BST → AVL → 红黑 → Trie
下一篇：S03-B08 · 位运算。
1. 一句话结论
图有两种存储、两种遍历、一类特殊问题（连通性）。并查集就是"只关心连通性"时最快的专门结构。
| 需求 | 用什么 |
|---|---|
| 任意两点最短路 | BFS（无权）/ Dijkstra（带权） |
| 遍历所有节点 | DFS / BFS |
| 动态加边 + 判断连通 | 并查集 |
| 任务依赖排序 | 拓扑排序 |
| 最小生成树 | Kruskal（并查集）/ Prim（堆） |
2. 两种存储：邻接矩阵 vs 邻接表
| 维度 | 邻接矩阵 n×n |
邻接表 List<List<Integer>> |
|---|---|---|
| 空间 | O(n²) | O(n + m)（m 为边数） |
| 判断 (u,v) 有边 | O(1) | O(degree) |
| 遍历邻居 | O(n)（含空位） | O(degree) |
| 适合 | 稠密图（m ≈ n²） | 稀疏图（m ≪ n²） |
判据：边数超过 n²/10 时考虑矩阵，否则邻接表。绝大多数业务图（社交、依赖、路由）都是稀疏的。
3. 并查集：实测三种实现的差距
3.1 原理
parent[i]：i 的父节点；根节点的parent[root] = root。find(x)：一路向上找根。union(a,b)：把两个根连起来。
3.2 实测（N=50,000，随机 union）
| 实现 | 耗时 | 相对 |
|---|---|---|
| 朴素（不压缩、不按秩） | 5,789 ms | 基准 |
| 仅路径压缩 | 185 ms | 31× 快 |
| 路径压缩 + 按秩合并 | 177 ms | 33× 快 |
结论：路径压缩是决定性的优化（把长链压成"几乎直接指向根"）；按秩合并在此基础上只再省 4%。
注意：这次测的是随机 union；如果是"构造出链式 union"的最坏情况，朴素实现会退化到 O(n) 每次。
3.3 为什么近似 O(1)
路径压缩 + 按秩合并后，单次操作的摊还复杂度是 O(α(n))，α 是反阿克曼函数——在 n < 10⁶⁰⁰ 时 α(n) ≤ 4。工程上就是 O(1)。
4. 图的两种遍历（写法与用途）
| 遍历 | 结构 | 用途 | 复杂度 |
|---|---|---|---|
| DFS | 栈（递归/显式栈） | 连通分量、环检测、拓扑排序、回溯 | O(n+m) |
| BFS | 队列 | 无权最短路、层序、连通分量 | O(n+m) |
关键区别：BFS 第一次到达某点就是最短路径（边权相等）；DFS 不保证。
// BFS 模板（无权最短路）
int[] dist = new int[n]; Arrays.fill(dist, -1);
Deque<Integer> q = new ArrayDeque<>();
dist[s] = 0; q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (dist[v] == -1) { dist[v] = dist[u] + 1; q.add(v); }
}
}
5. 拓扑排序与环检测（E-S03-010）
拓扑排序 = 把有依赖的有向图排成线性序列（任务调度、构建顺序、课程安排）。
| 方法 | 做法 | 特点 |
|---|---|---|
| Kahn（BFS） | 反复取入度为 0 的节点 | 天然支持"分层"；剩余节点即环 |
| DFS 后序 | 逆后序遍历 | 实现简洁；需三色标记检测环 |
判据：Kahn 的产物数量 < 节点总数 → 图中存在环。这也是"依赖循环"的检测方式（如 Maven 循环依赖、CI 任务环）。
6. 并查集的四个典型应用
| 场景 | 用法 |
|---|---|
| 判断连通分量个数 | 每次 union 成功 → 分量数减 1 |
| Kruskal 最小生成树 | 按边权排序，union 判断是否成环 |
| 账户合并（同一人的多个账号） | 把"同邮箱/同手机"的账号 union |
| 岛屿数量 / 连通区域 | 相邻格子 union |
注意边界：并查集不支持删除边（只支持加边）。需要动态删边时要用更复杂的结构（如 Link-Cut Tree）或离线处理。
7. 五个误区
| 误区 | 真相 |
|---|---|
| "并查集天然 O(1)" | 需要路径压缩（+按秩）；朴素实现实测慢 31× |
| "BFS 能算带权最短路" | 只适用于边权相等；带权要 Dijkstra |
| "邻接矩阵更清晰所以更好" | 稀疏图上空间 O(n²) 不可接受 |
| "DFS 能判环" | 无向图 DFS 会把"父边"误判成环，要记录父节点 |
| "并查集能删边" | 不能（只支持合并） |
8. 自检
- 邻接矩阵与邻接表怎么选？给出判据。
- 朴素并查集为什么慢？路径压缩怎么修？
- α(n) 是什么？为什么说工程上等于 O(1)？
- Kahn 算法怎么判断有环？
- 为什么带权最短路不能用 BFS？
9. 下一篇
S03-B08 · 位运算：用二进制位做集合
图与并查集处理"关系"，位运算处理"状态"。下一篇给出 6 个高频技巧与实测（10 万开关：布尔列表 781 KB vs 位掩码 12.2 KB），并说明什么时候位运算是必要的。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1509/1510；扩展点 E-S03-010。并查集实测（5,789 / 185 / 177 ms）为 2026-11-05。