Union Find 算法

从 30 年到 6 秒

作者 QIFAN 日期 2017-01-07
Union Find 算法

本文主要内容是经典算法 Union Find 的数组不同实现方式,以实例展示了一个算法分析优化的过程。

问题抛出

日常生活中经常会有找连接的问题,比如迷宫,运输,电路等等。核心主题是判断两点间的通路。常常需要高效率的算法来解决各点间的连通问题。

名词定义

连接体( connected component ) : 相互连接的最大对象集合。
根(root) : 序号与 id 相同的点,可以认为是一个 component 的顶点。

API

public class UF
UF(int N) // 构造器
void union(int p, int q) // 连接 p 与 q
boolean connected(int p, int q) // p ,q 是否连接
int find(int p) // 找到 p 所在的 connected component
int count() // connected component 数量

算法及改进

Quick Find

这个方法的底层就是一个一维数组 id ,初始值设为其位置序号。 构造数组的时间成本为 $O(n)$ 。

//initialize
public QuickFindUF(int n) {
id = new int[n];
for(int i = 0; i < n; i++) {
id[i] = i;
}
}

union(int p, int q) 意味着连接 p 、 q 两点,本文默认规则将 p 点的 id 改成 q 的的 id 。
该操作的时间复杂度为 $O(n)$ ,因为需要遍历数组找到属于 p 所在 component 内的所有点,并将这些点的 id 全部改变。

// 连接操作
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
// 把所有 pid 的点改为 qid
for(int i=0; i<id.length; i++) {
if(id[i]==pid) {
id[i] = qid;
}
}
}

判断两点是否相连只要看两点的id是否相同,若相同,则在同一个 connected component 。时间成本为 $O(1)$ 。

// 判断连接
public boolean connected(int p, int q) {
return id[p] == id[q];
}

find() :某一点所在的 component 即该点的 id ,时间成本为 $O(1)$ 。
count() : component 数量为数组中不同 id 的个数,需要遍历 component ,时间成本为 $O(n)$ 。

Quick Find 的 Java 实现: QuickFind.java

Quick Union

Quick find 在查找上展现了强劲的实力($O(1)$),但如果大多数的操作都是 union() ,则会很慢。
Quick Union 在 Quick Find 基础上改进了 union() ,连接操作时不必改变 component 中的所有 id ,只需改变该 component 的 root 的 id 。比如以下数组:

1 2 3 4 5 6 7 8
id 2 2 2 4 4 6 6 6

该数组中有以下三个 connected component :{1,2,3} , {4,5} , {6,7,8} 。
连接 3 和 4 , union(3,4) ,因为 3 的 root 为 2 , 4 的 root 为 4 ,所以改变 2 的值为 4 。:

1 2 3 4 5 6 7 8
id 2 4 2 4 4 6 6 6

再连接 1 和 7 , 1 的 root 为 4(1–>2–>4) , 7 的 root 为 6 ,改变 4 的值为 6 :

1 2 3 4 5 6 7 8
id 2 4 2 6 4 6 6 6

以上例子可以看出 i 的 root 是 id[id[..id[i]..]] (直到值与点相同)。

构造器:与 Quick Find 一样,时间成本为 $O(n)$ 。
新增 root 方法用于找到 i 的 root (与 find() 作用相同),成本取决于 component 的高度,最坏时间成本为 $O(n)$ 。

//找根
private int root(int i) {
while(i != id[i]) {
i = id[i];
}
return i;
}

union(p, q),分别找到 p , q 的 root ,并将 p 的 root 改为 q 的 root ,成本取决于 component 的高度,最坏时间成本为 $O(n)$ 。

/*
* Find the root of p and q, then make p's root's id connceted to q's root
*/
public void union(int p, int q) {
int i = root(p);
int j = root(q);
id[i] = j;
}

两点是否相连,只需判断是否有相同的 root 。成本取决于 component 的高度,最坏情况为 N 。

public boolean connected(int p, int q) {
return root(p) == root(q);
}

find(i) ,即 root(i)
count() ,不同 root 的个数 。

Quick Union 的 Java 实现: QuickUnion.java

Weighted Quick Union

Quick Union 在最坏情况下, union()find() 的时间复杂度为 $O(N)$ 。原因在于连接时 是可能不断的将高的树连接到矮的树上,导致 find() 花费久。

由此可以想到,如果能够避免将大树连接到小树,从而来保持一个较小的高度,进而减少 find() 成本。
Quick Union 的改进之一就是新增 size 变量来记录每个 component 的大小,避免将大树连接到小树上。

构造器:

//initialize
public QuickUnionUF(int n) {
id = new int[n];
size = new size[n];
for(int i = 0; i < n; i++) {
id[i] = i;
size[i] = 1;
}
}

union(p, q) :比较 q , p 所在 component 的 size ,将较小 component 的 root 改为较大 component 的 root 。
任意节点所在 component 的最大深度为 $logN$

证明
假设有树 T1 与树 T2 , T1.size < T2.size , 因此若 union(T1, T2) ,连接后的树高度加 1 ,而数的 size 却至少是之前的两倍,因此最多可以 double $logN$ 次,也就是树的高度最多可以增加 $logN$ 。

/*
* Find the root of p and q
* Compare the size of two roots
* Make smaller's root's id connceted to bigger's root
* Update bigger one's size
*/
public void union(int p, int q) {
int i = root(p);
int j = root(q);
if(i==j) return;
if(size[i] < size[j]) {
id[i] = j;
size[j] += size[i];
} else {
id[j] = i;
size[i] += size[j];
}
}

Path Compression

weighted quick union 解决了树太高的问题,但是每次操作还是需要重复的去计算 root ,如何减少重复运算次数?

改进方式:每次 root 某节点后,将该节点的父节点设为新的 root ,从而使连接体的树 更加平滑,减少深度。这样一个 union find 里,最多有一个 $logN$ 的查找,随着树深度的减少,最后 查找速度可以达到 Quick Find ,也就是 $O(1)$。 只需在 root 增加一步操作:

//chase root
private int root(int i) {
while(i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

总结

不同算法在最坏情况下时间( N 个对象, M 次 union-find 操作)

算法 最差时间复杂度
Quick Find $O(MN)$
Quick Union $O(MN)$
Weighted QU $O(N + MlogN)$
QU + Path Compression $O(N + MlogN)$
Weighted QU + Path Compression $N + MlogN$

若 $M=10^6$ , $N=10^6$

  • WQU + PC 使得计算时间从 30 年缩短到 6 秒
  • 再厉害的超级计算器都不如算法上一个小小的改变呀

阅读材料

Section 1.4 and 1.5 in Algorithms, 4th edition



References
Algorithms , Part I week 1 :https://www.coursera.org/learn/algorithms-part1/home/week/1



相关文章算法基础梳理



更新历史
+ 2016.10.19 第一版
+ 2017.01.07 格式修改