并查集路径压缩

曾经终败给现在 2024-03-16 23:49 46阅读 0赞

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

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

![0804fae4f994fc9f50a3ee1f64d6e7a9.png][]

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

![4f683c303225d10c499e35254b838e08.png][]

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

![799144281cc277037c15636308b5a762.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;  
>   
> \}

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

![9c0fd32305b753680ec0234ced20daf5.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 实例代码 ####

### 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的值  
> \}  
> \}  
> \}

[0804fae4f994fc9f50a3ee1f64d6e7a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2070231d25ff40c593b7c3a8f96b1cc6.png
[4f683c303225d10c499e35254b838e08.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/73de840ac76346c89103883352a2fc8f.png
[799144281cc277037c15636308b5a762.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/aecd7900130244beba88cd4604690eac.png
[9c0fd32305b753680ec0234ced20daf5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2854f7316c48461bb7a82a5f2dfd18d5.png