并查集 rank 的优化（Java 实例代码）

冷不防 2023-10-14 21:07 110阅读 0赞

**目录**

并查集 rank 的优化

Java 实例代码

UnionFind3.java 文件代码：

--------------------

## 并查集 rank 的优化 ##

上一小节介绍了并查集基于 size 的优化，但是某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。

![7561a182ed69e7dafb5bef57311d44d5.png][]

根据上一小节，size 的优化，元素少的集合根节点指向元素多的根节点。操作完后，层数变为4，比之前增多了一层，如下图所示：

![3fb31fb1d2b9eac6cddd03a4181a5e66.png][]

由此可知，依靠集合的 size 判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这就是基于 rank 的优化。

![56512f102f1baf3bf7b91a8c2c34d19b.png][]

我们在并查集的属性中，添加 rank 数组，rank\[i\] 表示以 i 为根的集合所表示的树的层数。

...  
private int\[\] rank; // rank\[i\]表示以i为根的集合所表示的树的层数  
private int\[\] parent; // parent\[i\]表示第i个元素所指向的父节点  
private int count; // 数据个数  
...

构造函数相应作出修改：

...  
// 构造函数  
public UnionFind4(int count)\{  
rank = new int\[count\];  
parent = new int\[count\];  
this.count = count;  
// 初始化, 每一个parent\[i\]指向自己, 表示每一个元素自己自成一个集合  
for( int i = 0 ; i < count ; i ++ )\{  
parent\[i\] = i;  
rank\[i\] = 1;  
\}  
\}  
...

合并两元素的时候，需要比较根节点集合的层数，整个过程是 O(h)复杂度，h为树的高度。

...  
public void unionElements(int p, int q)\{  
int pRoot = find(p);  
int qRoot = find(q);  
if( pRoot == qRoot )  
return;  
  
if( rank\[pRoot\] < rank\[qRoot\] )\{  
parent\[pRoot\] = qRoot;  
\}  
else if( rank\[qRoot\] < rank\[pRoot\])\{  
parent\[qRoot\] = pRoot;  
\}  
else\{ // rank\[pRoot\] == rank\[qRoot\]  
parent\[pRoot\] = qRoot;  
rank\[qRoot\] += 1; // 此时, 我维护rank的值  
\}  
\}  
...

#### Java 实例代码 ####

**源码包下载：**[Download][]

### UnionFind3.java 文件代码： ###

package runoob.union;  
/\*\*  
\* 基于rank的优化  
\*/  
public class UnionFind4 \{  
private int\[\] rank; // rank\[i\]表示以i为根的集合所表示的树的层数  
private int\[\] parent; // parent\[i\]表示第i个元素所指向的父节点  
private int count; // 数据个数  
// 构造函数  
public UnionFind4(int count)\{  
rank = new int\[count\];  
parent = new int\[count\];  
this.count = count;  
// 初始化, 每一个parent\[i\]指向自己, 表示每一个元素自己自成一个集合  
for( int i = 0 ; i < count ; i ++ )\{  
parent\[i\] = i;  
rank\[i\] = 1;  
\}  
\}  
// 查找过程, 查找元素p所对应的集合编号  
// O(h)复杂度, h为树的高度  
private int find(int p)\{  
assert( p >= 0 && p < count );  
// 不断去查询自己的父亲节点, 直到到达根节点  
// 根节点的特点: parent\[p\] == p  
while( p != parent\[p\] )  
p = parent\[p\];  
return p;  
\}  
// 查看元素p和元素q是否所属一个集合  
// O(h)复杂度, h为树的高度  
public boolean isConnected( int p , int q )\{  
return find(p) == find(q);  
\}  
// 合并元素p和元素q所属的集合  
// O(h)复杂度, h为树的高度  
public void unionElements(int p, int q)\{  
int pRoot = find(p);  
int qRoot = find(q);  
if( pRoot == qRoot )  
return;  
if( rank\[pRoot\] < rank\[qRoot\] )\{  
parent\[pRoot\] = qRoot;  
\}  
else if( rank\[qRoot\] < rank\[pRoot\])\{  
parent\[qRoot\] = pRoot;  
\}  
else\{ // rank\[pRoot\] == rank\[qRoot\]  
parent\[pRoot\] = qRoot;  
rank\[qRoot\] += 1; // 维护rank的值  
\}  
\}  
\}

[7561a182ed69e7dafb5bef57311d44d5.png]: https://img-blog.csdnimg.cn/img_convert/7561a182ed69e7dafb5bef57311d44d5.png
[3fb31fb1d2b9eac6cddd03a4181a5e66.png]: https://img-blog.csdnimg.cn/img_convert/3fb31fb1d2b9eac6cddd03a4181a5e66.png
[56512f102f1baf3bf7b91a8c2c34d19b.png]: https://img-blog.csdnimg.cn/img_convert/56512f102f1baf3bf7b91a8c2c34d19b.png
[Download]: https://www.runoob.com/wp-content/uploads/2020/10/runoob-algorithm-union.zip