Oneday
- 并查集的概述：他是一种特殊的树形结构，是一颗倒着的树，每个节点都是孩子指向父亲
- 并查集可以解决的问题：连接问题，用于看某两个节点是否有连接
- 并查集可以实现的操作：isConnected（）来看两个点是否在一个集合中、 union（）将两个节点的集合合并
- 并查集中数据的表示：
元素：0 1 2 3 4 5 6
id: 0 0 0 1 1 1 1 这里{0,1,2}属于0集合，{3,4,5,6}属于1集合
这是一个并查集的接口，后面所有的并查集类都实现了该接口
public interface UF {
//实现看两个ID的元素是否在一个集合中
boolean isConnected(int p,int q);
//将两个ID的元素的集合合并
void union(int p,int q);
//求并查集的大小
int getSize();
}
- 并查集的实现：（后面的所有的优化都是基于第二版的并查集实现的）
- QUICK FIND(这种方式是可以快速的查看两个元素之间的关系，但是合并比较慢)
isConnected（） 时间复杂度O（1）
union() 时间复杂度O（n）
//第一版并查集
/**
*
* @author jhd
*isConnected() 时间复杂度O(1)
*union() 时间复杂度O(n)
*/
public class UnionFind1 implements UF{
int []id;//设置每个元素对应的集合
public UnionFind1(int size) {
//由用户来提供大小，初始化id集合
id=new int[size];
for(int i=0;i<id.length;i++) {
id[i]=i;
}//初始化每个元素都属于自己的集合
}
@Override
public int getSize() {
return id.length;
}//实现获得并查集个数的函数
private int find(int p) {
if(p<0||p>id.length) {
throw new IllegalArgumentException("输入数据有误");
}
return id[p];
}//获得p元素所在的集合
@Override
public boolean isConnected(int p,int q) {
return find(p)==find(q);
}//用于看两个元素是否在一个集合中
@Override
public void union(int p,int q) {
int pID=find(p);
int qID=find(q);
if(pID==qID) {
return;
}//如果两个元素对应的id值相同，无需操作
for(int i=0;i<id.length;i++) {
if(id[i]==qID) {
id[i]=pID;
}
}//否则的话，将所有的qID变为pID，将两个集合合并
}
}
- QUICK UNION
isConnected（） 时间复杂度O（h） (h为树的高度)
union() 时间复杂度O（h）
//第二版并查集
/**
*
* @author jhd
*isConnected() 时间复杂度O(h)
*union 时间复杂度O(h)
*/
public class UnionFind2 implements UF{
int[]parent;//设置一个并查集，用于存储元素对应的父节点
public UnionFind2(int size) {
parent=new int[size];//根据用户提供的size初始化parent
for(int i=0;i<parent.length;i++) {
parent[i]=i;
}//初始化每个元素的根都是自己
}
@Override
public int getSize() {
return parent.length;
}
private int findRoot(int p) {
while(p!=parent[p]) {
p=parent[p];
}
return p;
}//这个函数是找到当前的这个节点的根节点
@Override
public boolean isConnected(int p,int q) {
return findRoot(p)==findRoot(q);
}//这时的判断两个元素是否在同一个集合是看它们的根节点是否相同
@Override
public void union(int p,int q) {
int pRoot=findRoot(p);
int qRoot=findRoot(q);
if(pRoot==qRoot) {
return;
}
parent[pRoot]=qRoot;
}//合并两个集合的操作就是找到它们的根节点，让其中一个根节点指向另一个根节点
}
-
基于size的优化
根据合并可以看出如果是这样的
image.png
image.png
那么不断的union 0，x，就会形成一个很长很长，，，的链表，这样对于查找根节点以及合并操作的时间都产生了很大的影响，所以在此时要设置一个数组，用于存储每个节点下的节点的个数，然后在合并的时候比较两个根节点下节点的大小，用小的指向大的，这样就可以减少h的大小，优化时间
//第三版并查集
//对于合并时的策略进行了修改，使得树的高度变小，时间复杂度变小
public class UnionFind3 implements UF{
int[]parent;//设置一个并查集，用于存储元素对应的父节点
int[]sz;//用于看当前的根下有几个节点
public UnionFind3(int size) {
parent=new int[size];//根据用户提供的size初始化parent
sz=new int[size];
for(int i=0;i<parent.length;i++) {
sz[i]=1;//初始化每一个根下的节点个数都为1
parent[i]=i;
}//初始化每个元素的根都是自己
}
@Override
public int getSize() {
return parent.length;
}
private int findRoot(int p) {
while(p!=parent[p]) {
p=parent[p];
}
return p;
}//这个函数是找到当前的这个节点的根节点
@Override
public boolean isConnected(int p,int q) {
return findRoot(p)==findRoot(q);
}//这时的判断两个元素是否在同一个集合是看它们的根节点是否相同
@Override
public void union(int p,int q) {
int pRoot=findRoot(p);
int qRoot=findRoot(q);
if(pRoot==qRoot) {
return;
}
if(sz[pRoot]<sz[qRoot]) {
parent[pRoot]=qRoot;
sz[qRoot]+=sz[pRoot];//更新q节点下的节点个数
}//如果p节点下的节点数小于q节点下的节点数，就让p节点指向q节点
else {
parent[qRoot]=pRoot;
sz[pRoot]+=sz[qRoot];
}//否则就让q节点指向p节点，并更新p节点下的节点数
}//合并两个集合的操作就是找到它们的根节点，让其中一个根节点指向另一个根节点
}
Twoday
-
基于rank的优化
首先今天对昨天的针对size的优化有了疑问，因为昨天对于size的优化是让根节点下节点少的指向节点多的，并维护size的值，但是如果情况是下图所示：
image.png
这时如果按照size的合并方法如果union（2,8），就是8指向7，但是这最后使得高度变大，所以这里引入了rank，这个rank在这里指的是树的最大的高度，也就是如果遇到两棵树的合并的问题，这时判断两棵树的高度的大小，如果A树>B树，那就让B节点指向A节点，如果A树<B树，就让A节点指向B节点，如果相等，前面的两种的任意一种都行，这时要维护rank，也就是根节点的最大高度要增1，前面的大于和小于的情况都无需维护rank，因为如果是大于或者小于，两棵树的最大高度的差要大于等于1，所以两棵树合并后最大高度较小的那棵树的现在的高度是他原来的最大高度加上现在的根节点也就是加1，所以顶多相等，就无须维护rank的值
//第四版并查集
//同样也是对合并时的操作进行修改，只不过现在是看树的高度，而不是看每个根节点的节点的个数，而是要看这个根节点的树的高度
public class UnionFind4 implements UF{
int[]parent;//设置一个并查集，用于存储元素对应的父节点
int[]rank;//存储某个根节点的树的最大的高度
public UnionFind4(int size) {
parent=new int[size];//根据用户提供的size初始化parent
rank=new int[size];
for(int i=0;i<parent.length;i++) {
rank[i]=1;//初始化每一个根节点的树的最大高度都为1
parent[i]=i;
}//初始化每个元素的根都是自己
}
@Override
public int getSize() {
return parent.length;
}
private int findRoot(int p) {
while(p!=parent[p]) {
p=parent[p];
}
return p;
}//这个函数是找到当前的这个节点的根节点
@Override
public boolean isConnected(int p,int q) {
return findRoot(p)==findRoot(q);
}//这时的判断两个元素是否在同一个集合是看它们的根节点是否相同
@Override
public void union(int p,int q) {
int pRoot=findRoot(p);
int qRoot=findRoot(q);
if(pRoot==qRoot) {
return;
}
if(rank[pRoot]<rank[qRoot]) {
parent[pRoot]=qRoot;
}//如果以p为根节点的树的最大的高度小于以q为根节点的树的最大的高度，就让p节点指向q节点
else if(rank[pRoot]>rank[qRoot]) {
parent[qRoot]=pRoot;
}//相反，就让q节点指向p节点
//以上的两种情况都无需维护rank，是因为添加另一颗比自己最大高度小的树，最多也就是与自己的最大高度相等，不可能大于，所以无需维护
else {
parent[qRoot]=pRoot;
rank[pRoot]+=1;
}//如果以p为根节点的树的最大高度等于以q为根节点的树的最大高度，这时无所谓p指向q还是q指向p，但是这时树的最大高度会自增1，维护rank
}//合并两个集合的操作就是找到它们的根节点，让其中一个根节点指向另一个根节点
}
-
路径压缩☆
这个是并查集中压缩高度比较重要的方法，其实操作只不过是在find函数中添加一步parent[x]=parent[parent[x]]，就是让当前要找的这个节点指向他父节点的父节点，这种方法并不能使得每个节点都指向最终的父节点，但是压缩了树的高度h，减小了时间的消耗，如下图，就是find(4)执行后的压缩情况：
image.png
对于这个路径压缩，里面会有一个问题值得思考，就是如果压缩路径，那么这棵树的最大的高度就会改变，这样不需要维护一下rank吗，其实是不用的，因为在合并的时候两者都要进行压缩，所以树的高度都会减少，所以rank在这里可以表示这棵树的高度的排名就好了，同上面一样，高度小的根节点指向高度大的根节点
//第五版并查集
//引入了路径压缩的概念
public class UnionFind5 implements UF{
int[]parent;//设置一个并查集，用于存储元素对应的父节点
int[]rank;//存储某个根节点的树的最大的高度
/*
* 对于此时的rank，肯定会有疑问，如果路径压缩那么这棵树的最大的高度肯定会改变，不需要维护rank吗
* ，在这里，是不需要维护的，因为这里的rank指的是以这个节点为根节点的高度的排名，而路径压缩并不会
* 改变它的排名，所以可以使用，无需维护
*/
public UnionFind5(int size) {
parent=new int[size];//根据用户提供的size初始化parent
rank=new int[size];
for(int i=0;i<parent.length;i++) {
rank[i]=1;//初始化每一个根节点的树的最大高度都为1
parent[i]=i;
}//初始化每个元素的根都是自己
}
@Override
public int getSize() {
return parent.length;
}
private int findRoot(int p) {
while(p!=parent[p]) {
parent[p]=parent[parent[p]];//这里使用路径压缩，使得此时的节点向上移动
p=parent[p];
}
return p;
}//这个函数是找到当前的这个节点的根节点
@Override
public boolean isConnected(int p,int q) {
return findRoot(p)==findRoot(q);
}//这时的判断两个元素是否在同一个集合是看它们的根节点是否相同
@Override
public void union(int p,int q) {
int pRoot=findRoot(p);
int qRoot=findRoot(q);
if(pRoot==qRoot) {
return;
}
if(rank[pRoot]<rank[qRoot]) {
parent[pRoot]=qRoot;
}//如果以p为根节点的树的最大的高度小于以q为根节点的树的最大的高度，就让p节点指向q节点
else if(rank[pRoot]>rank[qRoot]) {
parent[qRoot]=pRoot;
}//相反，就让q节点指向p节点
//以上的两种情况都无需维护rank，是因为添加另一颗比自己最大高度小的树，最多也就是与自己的最大高度相等，不可能大于，所以无需维护
else {
parent[qRoot]=pRoot;
rank[pRoot]+=1;
}//如果以p为根节点的树的最大高度等于以q为根节点的树的最大高度，这时无所谓p指向q还是q指向p，但是这时树的最大高度会自增1，维护rank
}//合并两个集合的操作就是找到它们的根节点，让其中一个根节点指向另一个根节点
}
-
路径压缩的延伸
这里还有另外的一种路径压缩的方式，是一种递归的方式，他可以实现将要查找的节点的所有的根节点除了最后的那一个都指向最后的根节点，如下图：
image.png
如果执行find（4）操作，就可以得到这样的结果
//第六版并查集
//引入了路径压缩的概念
public class UnionFind6 implements UF{
int[]parent;//设置一个并查集，用于存储元素对应的父节点
int[]rank;//存储某个根节点的树的最大的高度
/*
* 对于此时的rank，肯定会有疑问，如果路径压缩那么这棵树的最大的高度肯定会改变，不需要维护rank吗
* ，在这里，是不需要维护的，因为这里的rank指的是以这个节点为根节点的高度的排名，而路径压缩并不会
* 改变它的排名，所以可以使用，无需维护
*/
public UnionFind6(int size) {
parent=new int[size];//根据用户提供的size初始化parent
rank=new int[size];
for(int i=0;i<parent.length;i++) {
rank[i]=1;//初始化每一个根节点的树的最大高度都为1
parent[i]=i;
}//初始化每个元素的根都是自己
}
@Override
public int getSize() {
return parent.length;
}
private int findRoot(int p) {
if(p!=parent[p]) {
parent[p]=findRoot(parent[p]);
}//这里我们可以发现，find方法本来就是找当前的这个节点的根节点,故让当前的节点的根节点指向他的根节点的根节点
return parent[p];//否则找到了最后的根节点返回就可以了
//这个使用递归的方式来实现的路径压缩，可以使得根节点下的每一个节点都直接指向根节点
}//这个函数是找到当前的这个节点的根节点
@Override
public boolean isConnected(int p,int q) {
return findRoot(p)==findRoot(q);
}//这时的判断两个元素是否在同一个集合是看它们的根节点是否相同
@Override
public void union(int p,int q) {
int pRoot=findRoot(p);
int qRoot=findRoot(q);
if(pRoot==qRoot) {
return;
}
if(rank[pRoot]<rank[qRoot]) {
parent[pRoot]=qRoot;
}//如果以p为根节点的树的最大的高度小于以q为根节点的树的最大的高度，就让p节点指向q节点
else if(rank[pRoot]>rank[qRoot]) {
parent[qRoot]=pRoot;
}//相反，就让q节点指向p节点
//以上的两种情况都无需维护rank，是因为添加另一颗比自己最大高度小的树，最多也就是与自己的最大高度相等，不可能大于，所以无需维护
else {
parent[qRoot]=pRoot;
rank[pRoot]+=1;
}//如果以p为根节点的树的最大高度等于以q为根节点的树的最大高度，这时无所谓p指向q还是q指向p，但是这时树的最大高度会自增1，维护rank
}//合并两个集合的操作就是找到它们的根节点，让其中一个根节点指向另一个根节点
}
- 并查集的时间复杂度的分析：
在前面也有说明，并查集的时间复杂度为O(h)，但h的变化不定，所以并不能保证时间复杂度是多少，其实它的严格意义上的时间复杂度为O（log*n）,注意这个不是logn，这个函数分为两种情况，当n<=1时，log*0=0，当n>1时，log*n=1+log*(logn),上面的这些最终分析出来并查集的时间复杂度近乎等于O(1)，是比logn要快的
