算法——union-find
简介
今天跟大家分享一个算法，如题union-find。这个算法要解决的就是一个动态连通性问题，什么是动态连通性呢？首先是连通性，给出两个对象，可以判断两个对象是否相连；再有就是动态，如若给出的两个对象不相连，我们可以将他们连起来，于是连通的对象发生了变化，体现了动态。举个栗子来说，就像判断两个计算机能否实现通信，就是判断他们是否能够通过现有的线路相连，进行通信，如果不能通信就需要通过其他手段，如增加物理线路，增加路由等来使得两个计算机实现连接。在下边的叙述中，为了方便起见，我们把一个一个对象，或者一个一个计算机称为触点，相连的几个触点整体称为连通分量（简称分量）。
上面这个图有九个触点，三个分量
正文
首先给出初步算法实现：
public class UF {
private int[] id;//分量id
private int count;//分量数量
public UF(int N){
count = N;
id = new int[N];
for (int i=0;i<N;i++){
id[i] = i;
}
}
public int count(){
return count;
}
public boolean connected(int p,int q){
return find(p) == find(q);
}
public int find(int i){
return id[i];
}
public void union(int p,int q){
int pID = find(p);
int qID = find(q);
if (pID == qID)return;
for (int i=0;i<id.length;i++){
if (id[i]==pID) id[i]=qID;
}
count--;
}
public static void main(String[] args) {
int[] array = {4,3,3,8,6,5,9,4,2,1,8,9,5,0,7,2,6,1,1,0,6,7};
UF uf = new UF(10);
for (int i = 0;i<array.length-1;i=i+2){//A
if (uf.connected(array[i],array[i+1])) continue;
uf.union(array[i],array[i+1]);
System.out.println("union"+array[i]+"and"+array[i+1]);
}
System.out.println("共"+uf.count()+"个连通分量");
}
}首先需要明白在这个实现中，id这个数组的索引代表的就是上文所说的触点。count表示的就是分量的数量。初始化时，有N个分量，每个分量中只有一个触点。判断两个触点i和j是否相连，就看id[i]和id[j]的值是否相等。最开始每个触点各成一个分量，于是都各不相连。当我们需要连接两个触点的时候，就要将值为id[i]的触点的值改为id[j](有点拗口，代码更清晰)，当然反过来亦可。今天主要需要讨论的就是find和union的不同实现。上面这个实现被称为quick-find，顾名思义，显然find()方法的速度是很快的，它只需要访问id数组一次。但是，union()则需要扫描整个数组。当id[]过长，需要处理大量数据时，这个算法实现明显是不可以胜任的。
quick-union成为了下一步的探索
public int find(int i){
while (i!=id[i]) i = id[i];
return i;
}
public void union(int p,int q){
int pRoot = find(p);
int qRoot = find(q);
if (pRoot==qRoot) return;
id[pRoot] = qRoot;
count--;
}在quick-union这个实现中，union()不再需要遍历整个数组，看起来要比quick-find快很多。在这个算法实现中使用森林来组织所有的触点，相连的触点会组织成一棵树。不相连的触点就会位于不同的树上面。此算法中的find就是寻找触点的根触点（根触点就是id[i]=i的点），也就是树的根。union()就是判断两个触点是否是一颗树上的节点，如果不是，那就将一棵树作为子树连接到另一颗树上面。如下图所示，当运行main函数时，随着A处循环的进行，过程如下(公众号回复quick-union可查看动画演示)
可惜这个算法实现的效率跟输入的触点有很大的关系，比如，最坏情况下会出现这样的树
此时我们就需要再次改进算法，于是出现了加权quick-union算法。
private int find(int p){
while (p != id[p])p = id[p];
return p;
}
public void union(int p,int q){
int j = find(p);
int i = find(q);
if (i == j) return;
if (sz[i]<sz[j]) {
id[i] = j;
sz[j] += sz[i];
}
else {
id[j] = i;
sz[i] += sz[j];
}
count--;
}这个算法改进的一点就是在连接两颗树的时候，先判断树的大小，保证将小数连在大树上，从而减小树的深度，提高效率。在这个算法中新增了一个实例变量sz[]，这个数组用来保存每个树的大小，从而方便操作。
此时这个算法已经可以处理大量的数据了。但没有最好，只有更好，更优秀的算法实现送给大家----使用路径压缩的加权quick-union算法：
private int find(int p){
while (p != id[p])
{
id[p] = id[id[p]]
p = id[p];
}
return p;
}只是在find()方法中加了一行代码，这行代码的用处就是将p的父节点设置成他的爷爷节点，最终P就会直接连在根节点上，从而路径被压缩，再次提高了效率。
这里没有用数学语言严谨的讨论每种实现的效率，复杂度等。各种算法的时间复杂度如下：
参考自《算法》，需要pdf版书籍请公众号直接回复 算法
如果您喜欢这篇文章，期待您的关注