Union-Find Algorithm-并查集

目录

1.概念

2.并查集的优化

1.路径压缩（Path Compression）

1）隔代压缩：

2）完全压缩：

2.按秩合并

1.概念

并查集：用于判断一对元素是否相连，它们的关系是动态添加（一边查询一边合并）的，这一类叫做动态连通性问题

作用：支持元素的合并、查询是否在同一个集合

        合并：将一个集合的根节点指向另一个集合的根节点，当根结点相同就说明在同一个集合中

数据结构：数组或哈希表；表示节点指向的父节点，初始化时指向自己

2.并查集的优化

1.路径压缩（Path Compression）

核心思想：只关心两个顶点的连通性，而不关心两个顶点之间的距离

        为了避免并查集所表示的树形结构高度过高，影响查询性能，我们在查询的过程中使用路径压缩将不同变量转换为同一个变量，从而降低树的高度

1）隔代压缩：

        将一个节点指向它的父节点的父节点，然后对该节点新的父节点执行隔代压缩，令其指向它的父节点的父节点，依次类推直到指向根节点（体现了核心思想：只关注连通性，不关注如何连通的）

                                        压缩前                                                            压缩后

代码实现：

//parent[a] = b，表示：结点 a 的（直接）父亲结点是 b
//隔代压缩
public int find(int x){
    while(x != parent[x]){
       parent[x] = parent[parent[x]];
       x = parent[x];
    }
    return x;
}

2）完全压缩：

        将节点到根节点沿途经过的节点都指向根节点；

如下图：在查询节点4的根节点的同时，将节点4到根节点的沿途所有节点的父亲节点都指向根节点，特殊情况下，根节点的父节点就是根节点自己；从而使得路径压缩后的树的高度均为2

                                        压缩前                                                            压缩后

代码实现：需要借助递归算法

//完全压缩
public int find(int x){
   if(parent[x] != x){
       parent[x] = find(parent[x]);
   }
   return parent[x];
}

一般来说：完全压缩的效率并不如隔代压缩，且隔代压缩多执行几次也能够达到完全压缩的效果

2.按秩合并

核心思想：合并过程中，将高度较小的树的根节点指向高度较大的根节点，从而避免合并后树的高度增加

秩：以当前节点为根节点的树的高度；或者是以当前节点为根节点的树的节点的个数

注意：当同时使用路径压缩和按秩合并时，难以维护秩的准确定义，因此一般不维护；且合并与查询的时间复杂度接近O(1)