今天跟大家分享一个算法,如题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版书籍请公众号直接回复 算法
如果您喜欢这篇文章,期待您的关注