一、动态连通性
这一篇对应官方 Lecture 14(Disjoint Sets)。
设想一个网络,节点之间不断建立连接。要求是:无论连接怎么加,随时能回答「A 和 B 现在是否连通」。
朴素做法是每次查询都做一次搜索,但连接一多,每次都要重算。并查集换了一个思路:只维护「谁属于哪个集合」,把连通性变成「是否有同一个根」。
它只需要两个操作:
| 操作 |
语义 |
connect(a, b) |
把 a 与 b 所在的集合合并 |
isConnected(a, b) |
判断 a 与 b 是否在同一集合 |
二、第一代:Quick-Find
最直接的想法是开一个 id[] 数组,id[i] 直接存 i 所属集合的编号。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
| import java.util.Arrays;
public class DisjointSets { static class QuickFind { int[] id; long ops = 0;
QuickFind(int n) { id = new int[n]; for (int i = 0; i < n; i += 1) { id[i] = i; } }
boolean isConnected(int a, int b) { ops += 1; return id[a] == id[b]; }
void connect(int a, int b) { int aid = id[a]; int bid = id[b]; for (int i = 0; i < id.length; i += 1) { ops += 1; if (id[i] == aid) { id[i] = bid; } } } }
static class QuickUnion { int[] parent; long ops = 0;
QuickUnion(int n) { parent = new int[n]; for (int i = 0; i < n; i += 1) { parent[i] = i; } }
int find(int x) { while (x != parent[x]) { ops += 1; x = parent[x]; } return x; }
boolean isConnected(int a, int b) { return find(a) == find(b); }
void connect(int a, int b) { parent[find(a)] = find(b); } }
static class WeightedQuickUnion { int[] parent; int[] size; long ops = 0;
WeightedQuickUnion(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i += 1) { parent[i] = i; size[i] = 1; } }
int find(int x) { while (x != parent[x]) { ops += 1; x = parent[x]; } return x; }
boolean isConnected(int a, int b) { return find(a) == find(b); }
void connect(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) { return; } if (size[ra] < size[rb]) { parent[ra] = rb; size[rb] += size[ra]; } else { parent[rb] = ra; size[ra] += size[rb]; } } } }
|
QuickFind 的取舍一目了然:isConnected 是一次数组比较,O(1);但 connect 必须扫描整个数组把旧的集合编号全部改掉,O(N)。连接一多,代价就集中到合并上。
三、第二代:Quick-Union
把 id[] 换成 parent[],让每个节点指向父节点,根节点指向自己。判断连通就变成「两个节点的根是否相同」。
connect 只做一件事:parent[find(a)] = find(b),O(1)。代价转移到了 find——它要沿着父指针一路向上,步数等于树高。
代价到底差多少?用同一组「链式连接」实测:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| int small = 8; QuickUnion qu = new QuickUnion(small); WeightedQuickUnion wqu = new WeightedQuickUnion(small); for (int i = 0; i < small - 1; i += 1) { qu.connect(i, i + 1); wqu.connect(i, i + 1); } System.out.println("依次 connect(0,1), connect(1,2), ... connect(6,7):"); System.out.println(" QuickUnion parent = " + Arrays.toString(qu.parent)); System.out.println(" Weighted parent = " + Arrays.toString(wqu.parent)); System.out.println(" Weighted size = " + Arrays.toString(wqu.size));
int n = 4096; QuickUnion q2 = new QuickUnion(n); WeightedQuickUnion w2 = new WeightedQuickUnion(n); for (int i = 0; i < n - 1; i += 1) { q2.connect(i, i + 1); w2.connect(i, i + 1); } q2.ops = 0; w2.ops = 0; for (int i = 0; i < n; i += 1) { q2.isConnected(0, i); w2.isConnected(0, i); } QuickFind qf = new QuickFind(n); for (int i = 0; i < n - 1; i += 1) { qf.connect(i, i + 1); } System.out.println("N = " + n + ",链式 connect 后做 " + n + " 次 isConnected(0, i):"); System.out.println(" QuickUnion 查找步数 = " + q2.ops); System.out.println(" Weighted 查找步数 = " + w2.ops); System.out.println(" 同一序列下 QuickFind 合并步数 = " + qf.ops);
|
输出:
1 2 3 4 5 6 7 8
| 依次 connect(0,1), connect(1,2), ... connect(6,7): QuickUnion parent = [1, 2, 3, 4, 5, 6, 7, 7] Weighted parent = [0, 0, 0, 0, 0, 0, 0, 0] Weighted size = [8, 1, 1, 1, 1, 1, 1, 1] N = 4096,链式 connect 后做 4096 次 isConnected(0, i): QuickUnion 查找步数 = 25159680 Weighted 查找步数 = 4095 同一序列下 QuickFind 合并步数 = 16773120
|
QuickUnion 的 parent 数组是 [1, 2, 3, 4, 5, 6, 7, 7]——一条不折不扣的链。查找 0 必须走 7 步。放大到 N = 4096 后,这个链条让 4096 次查询累计走了 25,159,680 步。
四、第三代:加权合并
问题出在合并策略上。parent[find(a)] = find(b) 是「谁先来谁当父节点」,完全不管两棵树的大小,于是很容易长出长链。
改进只有一句:把小树挂到大树下面。
flowchart TB
A["合并前:两棵树,大小 1 和 4"] --> B["若把大树挂到小树<br/>树高变成 5"]
A --> C["若把小树挂到大树<br/>树高仍是 max(1, 4+1)"]
B --> D["最坏可退化成链"]
C --> E["树高被限制在 log N"]
为什么树高能压到 O(log N)?因为每次一个节点所在树的深度增加 1,说明它所在的树至少翻了一倍(它从小树并入了至少同样大的大树)。一个节点最多只能这样翻 log₂N 次。
实测数据很直接:同一组连接、同一组查询,查找步数从 25,159,680 降到 4,095,相差约 6100 倍。
三代实现的取舍可以总结成一张表:
| 实现 |
connect 代价 |
isConnected 代价 |
最坏情况 |
| Quick-Find |
O(N) |
O(1) |
合并退化 |
| Quick-Union |
O(1)(不计 find) |
O(树高),最坏 O(N) |
查询退化 |
| 加权 Quick-Union |
O(log N) |
O(log N) |
树高有上界 |
五、路径压缩:查一次,顺手把路径压平
加权合并把树高压到了 log N,但还有一层改进空间:既然查找必须走完整条路径,为什么不顺手把路径上的节点直接挂到根上?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
| import java.util.Arrays;
public class PathCompression { static class Weighted { int[] parent; int[] size; long ops = 0;
Weighted(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i += 1) { parent[i] = i; size[i] = 1; } }
int find(int x) { while (x != parent[x]) { ops += 1; x = parent[x]; } return x; }
void connect(int a, int b) { int ra = find(a); int rb = find(b); if (ra == rb) { return; } if (size[ra] < size[rb]) { parent[ra] = rb; size[rb] += size[ra]; } else { parent[rb] = ra; size[ra] += size[rb]; } } }
static class WeightedCompressed extends Weighted { long compressOps = 0;
WeightedCompressed(int n) { super(n); }
@Override int find(int x) { int root = x; while (root != parent[root]) { ops += 1; root = parent[root]; } while (x != root) { int nxt = parent[x]; if (parent[x] != root) { parent[x] = root; compressOps += 1; } x = nxt; } return root; } }
public static void main(String[] args) { int n = 16; int[][] pairs = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 11}, {12, 13}, {14, 15}, {0, 2}, {4, 6}, {8, 10}, {12, 14}, {0, 4}, {8, 12}, {0, 8}};
Weighted a = new Weighted(n); WeightedCompressed b = new WeightedCompressed(n); for (int[] p : pairs) { a.connect(p[0], p[1]); b.connect(p[0], p[1]); } System.out.println("平衡合并后 parent = " + Arrays.toString(a.parent));
a.ops = 0; a.find(7); System.out.println("无压缩 find(7) 第 1 次步数 = " + a.ops);
b.ops = 0; b.compressOps = 0; b.find(7); System.out.println("有压缩 find(7) 第 1 次:走链 " + b.ops + " 步,改写 " + b.compressOps + " 个指针"); System.out.println("有压缩 parent(压缩后)= " + Arrays.toString(b.parent));
b.ops = 0; b.find(7); System.out.println("有压缩 find(7) 第 2 次步数 = " + b.ops); } }
|
输出:
1 2 3 4 5
| 平衡合并后 parent = [0, 0, 0, 2, 0, 4, 4, 6, 0, 8, 8, 10, 8, 12, 12, 14] 无压缩 find(7) 第 1 次步数 = 3 有压缩 find(7) 第 1 次:走链 3 步,改写 2 个指针 有压缩 parent(压缩后)= [0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 8, 10, 8, 12, 12, 14] 有压缩 find(7) 第 2 次步数 = 1
|
先看第一行 parent 数组:路径 7 → 6 → 4 → 0,高度 3,正好是 log₂16。这就是加权合并的效果。
再看压缩后的数组:parent[7] 和 parent[6] 都变成了 0。第一次查找走 3 步,第二次只需要 1 步。 压缩的代价是写几个指针,收益是后续所有经过这条路径的查询都变快。
把两者叠加,均摊后的查找代价接近常数——精确上界是阿克曼反函数 α(N),对任何现实规模的输入都不超过 5,可以当作 O(1) 处理。
六、小结
| 概念 |
一句话 |
证据 |
| Quick-Find |
查找 O(1),合并 O(N) |
4095 次链式合并共 16,773,120 步 |
| Quick-Union |
合并 O(1),查找 O(树高) |
链式合并后 parent = [1..7, 7] |
| 加权合并 |
小树挂大树,树高降到 O(log N) |
查找步数 25,159,680 → 4,095 |
| 路径压缩 |
查找时把路径上节点挂到根 |
第二次 find(7) 从 3 步降到 1 步 |
| 叠加效果 |
均摊接近 O(1),上界为 α(N) |
α(N) 在现实中 ≤ 5 |
三条能带走的:
- 数据结构的最坏情况由「合并策略」决定,不是由存储形式决定。
parent[] 数组本身没问题,出问题的是「谁当父节点」这条规则。
- 加权给出的是可证明的上界,压缩给出的是实践中的常数。 两者叠加才得到几乎常数的操作代价。
- 「顺手做一件额外的事」是经典优化模式。 查找本来就要走这条路径,压缩是零边际成本的改进——这类机会在实现里值得刻意去找。