算法1.5union-find算法实现（加权quick-union算法）
《算法》笔记导航
《算法》中文第四版P145
2020.7.9
@Stream_
public class WeightedQuickUnionUF
连通问题：检测节点a和b是否相连（find(a)?=find(b)）
以某节点的名来表示互相连通：find节点a和find(b)都为a，则a，b相连
树的大小：节点的数量。树的深度：它到它的根节点的链接数。树的高度：它的所有节点的最大深度
以树来储存：树根唯一，并保证节点少的树连接到节点多的树上
一句两句无法完全解释清晰，只把算法的特性尽量简洁写出来，所以本笔记只适合在看完书后，忘记的时候回顾作用
一、变量，方法，类及其作用
1.变量
-
private int[] id
保存父节点（树）
例如a,b,c相连，id[a]=b,id[b]=c,id[c]=c，a的父节点是b，b的父节点是c，因为c是根节点，所以id[c]=c，所以c就是三个节点的“触点”。（当然也可能出现id[a]=c,id[b]=c,id[c]=c或其他的情况，树的定义要到下一章） -
private int[] sz
各个根节点所对应的分量的大小
这里储存的树的大小，代表节点数，（把sz改成public，union之后输出一下它的sz）要把小树连接到大树的根节点上 -
private int count;
触点的数量
触点就是有多少个不互相连通的部分（初值为初始化时点的个数）每次连通未曾连通的两个部分，数值减一
2.方法
2.1 普通方法
-
public int count()
返回触点的数量 -
public boolean connected(int p,int q)
检测节点p和节点q是否连通
通过检测两个节点的id的根是否相同实现
2.1 重要方法
-
public int find(int p)
查找节点p的根节点
通过循环获取p的父节点，直至到根节点（它的父节点是它本身）实现 -
public void union(int p,int q)
将节点p和q连通
将小树的根节点连接到大树的根节点上（尽量减小树的高度和大小，方便find进行查找）sz的大小表示树的大小（这棵树有多少子树节点）
二、算法的实现
public class WeightedQuickUnionUF {
private int[] id;
private int[] sz;
//在测试的时候改成了public，用于检测是否是小树连接到大树上
private int count;
public WeightedQuickUnionUF(int N){
count=N;
id=new int[N];
for(int i=0;i<N;i++){
id[i]=i;
}
sz=new int[N];
for(int i=0;i<N;i++){
sz[i]=1;
}
}
public int count(){
return count;
}
public int find(int p) {
while(p!=id[p]){
p=id[p];
}
return p;
}
public boolean connected(int p,int q){
return find(p)==find(q);
}
public void union(int p,int q){
int i=find(p);
int j=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--;
}
}
三、算法的使用
1.main函数
public static void main(String[] args) {
WeightedQuickUnionUF wqu=new WeightedQuickUnionUF(10);
//要把sz改成public，方便观察
wqu.union(0,1);
System.out.println(wqu.sz[0]+","+wqu.sz[1]);
wqu.union(2,3);
System.out.println(wqu.sz[2]+","+wqu.sz[3]);
wqu.union(4,5);
System.out.println(wqu.sz[4]+","+wqu.sz[5]);
wqu.union(6,7);
System.out.println(wqu.sz[6]+","+wqu.sz[7]);
//这里选用的数据用于说明的是sz表示的是树的大小，因为连接的是相同大小的树，所以可以换成不一样大小的树相连，查看是否是小树连接到大树的根节点
wqu.union(0,2);
System.out.println(wqu.sz[0]+","+wqu.sz[2]);
wqu.union(4,6);
System.out.println(wqu.sz[4]+","+wqu.sz[6]);
wqu.union(0,4);
System.out.println(wqu.sz[0]+","+wqu.sz[4]);
}
2.输出的数据
2,1
2,1
2,1
2,1
4,2
4,2
8,4
渣渣菜鸡，难免错误，请友善讨论
非商用转载需注明作者及文章链接来源，私信告知后无需我回复即可直接转载
