Dynamic connectivity (动静连通性)
We assume "is connected to" is an equivalence relation
- 自反性 Reflexive:
p is connected to p.
- 对称性 Symmetric:
if p is connected to q, then q is connected to p.
- 传递性 Transitive:
if p is connected to q and q is connected to r, then p is connected to r.
Quick Find (eager algorithm)
public class QuickFindUF { private int[] id; public QuickFindUF(int N) { id = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; } } public boolean connected(int p, int q) { return (id[p] == id[q]); } public void union(int p, int q) { int p_root = id[p]; int q_root = id[q]; for (int i = 0; i < id.length; i++) { if (id[i] == p_root){ id[p] = q_root; } } }}Takes N^2 array accesses to process sequence of N union commands on N objects.(quadratic time is much to slow)
Quick Union (lazy approach)
package com.algorithm.week1;public class QuickUnionUF{ private int[] id; public QuickUnionUF(int N) { id = new int[N]; // 设置每个对象的id为本人的初始索引（n次数组拜访） for (int i = 0; i < N; i++) { id[i] = i; } } private int root(int i) { // id[i] 是 i 的父节点，一直获取父节点直到达到根节点（获取的父节点不再变动） // 数组的拜访次数取决于 i 的父节点的深度 // 7 // / \ // 3 4 // / \ \ // 5 6 1 // 例如上图 i 为 5 时父节点深度为 3 // 过程如下 // i: 5 id[5]: 3 => i: 3 id[3]: 7 => i: 7 id[7]: 7 => return 7 while (i != id[i]){ i = id[i]; } return i; } public boolean connected(int p, int q) { // 查看 p 和 q 两者的根节点是否统一 // 数组的拜访次数取决于 p 和 q 父节点的深度 return root(p) == root(q); } public void union(int p, int q) { // 数组的拜访次数取决于 p 和 q 父节点的深度 int p_root = root(p); int q_root = root(q); // 将p的根节点指向q的根节点（p和q） id[p_root] = q_root; }}| algorithm | initialize | union | find |
|---|---|---|---|
| quick-find | N | N | 1 |
| quick-union (worst case) | N | N† († includes cost of finding roots) | N |
Quick-find 毛病
- Union 动作消耗较大（N次）
- Trees 扁平，然而维持扁平的代价太大（须要for循环遍历更新每个元素更新父节点）
Quick-union 毛病
- Trees 能够变得相当高
- Find 代价太大（可能达到N次）