并查集路径压缩（Java 实例代码）

我会带着你远行 2023-10-14 21:07 5阅读 0赞

**目录**

并查集路径压缩

Java 实例代码

UnionFind3.java 文件代码：

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

## 并查集路径压缩 ##

并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。

如下图中，find(4) 的过程就可以路径压缩，让数的层数更少。

![b73a5a6a2514d6570c49f8a8cfba1199.png][]

节点 4 往上寻找根节点时，压缩第一步，树的层数就减少了一层：

![dd4b7a55bdb3d579f0cd36f0f26542bf.png][]

节点 2 向上寻找，也不是根节点，那么把元素 2 指向原来父节点的父节点，操后后树的层数相应减少了一层，同时返回根节点 0。

![4ba799185fbdd06993b533b577efb01f.png][]

find 过程代码修改为 ：

// 查找过程, 查找元素p所对应的集合编号  
// O(h)复杂度, h为树的高度  
private int find(int p)\{  
assert( p >= 0 && p < count );  
  
// path compression 1  
while( p != parent\[p\] )\{  
parent\[p\] = parent\[parent\[p\]\];  
p = parent\[p\];  
\}  
return p;  
  
\}

上述路径压缩并不是最优的方式，我们可以把最初的树压缩成下图所示，层数是最少的。

![ada2100a73f1cd16278f193c38f15312.png][]

这个 find 过程代表表示为:

...  
// 查找过程, 查找元素p所对应的集合编号  
// O(h)复杂度, h为树的高度  
private int find(int p) \{  
assert (p >= 0 && p < count);  
  
//第二种路径压缩算法  
if (p != parent\[p\])  
parent\[p\] = find(parent\[p\]);  
return parent\[p\];  
\}  
...

#### 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;  
  
//第二种路径压缩算法  
//if( p != parent\[p\] )  
//parent\[p\] = find( parent\[p\] );  
//return parent\[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的值  
\}  
\}  
\}

[b73a5a6a2514d6570c49f8a8cfba1199.png]: https://img-blog.csdnimg.cn/img_convert/b73a5a6a2514d6570c49f8a8cfba1199.png
[dd4b7a55bdb3d579f0cd36f0f26542bf.png]: https://img-blog.csdnimg.cn/img_convert/dd4b7a55bdb3d579f0cd36f0f26542bf.png
[4ba799185fbdd06993b533b577efb01f.png]: https://img-blog.csdnimg.cn/img_convert/4ba799185fbdd06993b533b577efb01f.png
[ada2100a73f1cd16278f193c38f15312.png]: https://img-blog.csdnimg.cn/img_convert/ada2100a73f1cd16278f193c38f15312.png
[Download]: https://www.runoob.com/wp-content/uploads/2020/10/runoob-algorithm-union.zip