阅读 63

31-并查集(Union Find)

并查集(Union Find)

需求分析

假设现在有这样一个需求,如下图的每一个点代表一个村庄,每一条线就代表一条路,所以有些村庄之间有连接的路,有些村庄没有连接的路,但是有间接连接的路

根据上面的条件,能设计出一个数据结构,能快速执行下面2个操作

  1. 查询两个村庄之间是否有连接的路
  2. 连接两个村庄

为了完成上面的需求,能不能使用前面介绍的数据结构呢,例如:数组,链表,平衡二叉树,集合?其实是可以的,只是效率上高与低的问题。

例如使用动态数组完成上面这种操作,可以通过下面的方式完成。

  1. 将每个图用一个数组来对应,所以在这里,需要三个数组
    • 判断两个村庄之间是否有连接的路 判断两个元素是否在同一个数组中即可,如果两个元素在同一个元素中,就代表它们之间,有连接的路,否则就没有
    • 连接两个村庄 将两个村庄的元素,整合到一个数组即可

其他几种数据结构操作也类似。但是使用这些数据结构存在一个问题,它们的查询,连接时间复杂度都是O(n),所以用这些数据结构来完成上面的需求,不合适。但是在本节内容中介绍的并查集能够办到查询,连接的均摊时间复杂度都是O(α(n)),α(n) < 5,所以并查集非常适合解决这类“连接”相关的问题

并查集

并查集和叫做不相交集合(Disjoint Set)

并查集有2个核心操作

  1. 查找(Find):查找元素所在的集合(这里的集合并不是特指Set这种数据结构,是指广义上的数据集合)
  2. 合并(Union):将两个元素所在的集合合并为一个集合

并查集有2种常见的实现思路

  1. Quick Find
    • 查找(Find)的时间复杂度为:O(1)
    • 合并(Union)的时间复杂度为:O(n)
  2. Quick Union
    • 查找(Find)的时间复杂度为:O(logn),可以优化至O(α(n)),α(n) < 5
    • 合并(Union)的时间复杂度为:O(logn),可以优化至O(α(n)),α(n) < 5

所以,通过Quick Find来实现并查集的话,查找的效率会比Quick Union高,但是合并效率会比Quick Union低,那在开发中用哪一个呢?在开发中,一般使用Quick Union这种思路

并查集如何存储数据

现假设并查集处理的数据都是整型,那么可以用整型数组来存储数据,其中数组的索引代表对应的元素编号,然后数组中存储的数据为该元素对应所在的集合,所以如果用下图来表示对应村庄对应的集合,其中索引代表村庄的标号,编号对应的值代表村庄所在的集合

可以知道,村庄0,1,3是相互有路相连,村庄2/5分别独立,没有路与其他相连,村庄5,6,7是相互有路相连的。那么如果使用形象的图来表示的话,村庄0,1,3,可以用下图来进行表示

解释:

  1. 村庄索引0的父节点为村庄索引1
  2. 村庄索引3的父节点为村庄索引1
  3. 村庄索引1·的父节点为村庄索引1

也可以认为,索引对应的元素,代表父节点的索引,所以每一个节点,都有一根线,指向其父节点,所以从这个图,可以看出,0,1,3的父节点都1,所以属于同一个集合。以此类推2表示单独的一个集合

根据上面的定义,索引4的村庄的父节点索引为5,所以其实索引4与5之间是有联系的,并且5,6,7,之间本来也存在联系,所以最终可以用下图来进行表示,所以可以认为4,5,6,7也是属于同一个集合的。

所以,如果并查集是整数的话,就可以通过数组来表示每个元素之间的关系。所以并查集是可以用数组来实现的树形结构(二叉堆,优先级队列也是可以用数组实现的树形结构)

接口定义

所以,根据前面的介绍,并查集需要定义以下接口

/**
 * 查找v所属的集合(根节点)
 */
int find(int v);
/**
 * 合并v1,v2所属的集合
 */
void union(int v1, int v2);
/**
 * 检查v1,v2是否属于同一个集合
 */
boolean isSame(int v1, int v2);
复制代码
初始化

前面介绍了并查集的两种实现方式,不过,不管是使用哪种方式实现,都需要对数据进行初始化,初始化时,每个元素各自属于一个单元素集合。例如开始的时候,有如下的5个节点,其中索引0的元素存储元素0,索引1的元素存储元素1,索引2的元素存储元素2,索引3的元素存储元素3,索引4的元素存储元素4

然后用图来表示如下,其中,每一个元素属于一个单元素集合,即自己成为一个集合,这样代表所有的元素都不在同一个集合内。

所以初始化的实现代码为

public UnionFind(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity must be >= 1");
    }

    parents = new int[capacity];
    for (int i = 0; i < parents.length; i++) {
        parents[i] = i;
    }
}
复制代码
Quick Find - Union

在使用Quick Find实现上图的元素时,首先要进行的是初始化,前面已经介绍过了,所以在这里就不再赘述。初始化完成后,如果现在需要对1,0执行Union操作的话,有两种做法,即将0的箭头,指向1,或者将1的箭头指向0,这样就代表两个元素属于同一个集合中。现规定,如果执行union(v1,v2)的话,统一将v1的箭头指向v2。所以,如果现在执行union(1,0)操作的话,只需要将索引为1指向的元素,值改为0即可。即下图所示

对应的关系图如下

同样的,如果要执行union(1,2)操作的话,按照上面的操作,就是将索引为1指向的元素,改为2即可

但是修改后有一个问题,在以前,0,1是属于同一个集合的,现在1,2要变为同一个集合,所以还需要将索引0指向的元素也修改为2

最终的关系图如下

执行union(4,0)操作的话,根据上面的流程,最终得到的结果为

对应的关系图如下

执行union(3,2),得到的结果为

执行完成后得到的关系图如下

所以,发现细节了吗?使用Quick Find来实现Union的话,得到的结果很平,每一个节点,向上找一次,就能找到自己的根节点。那基于这种条件,继续在研究如何实现Find操作

所以合并的实现代码为

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    for (int i = 0; i < parents.length; i++) {
        if (parents[i] == p1) {
            parents[i] = p2;
        }
    }
}
复制代码
Quick Find - Find

如果使用的是上面这种Union方式,可以发现,数组中存储的数据,就是每个索引元素对应的根节点,所以如果有下图的元素

对应的关系图为

所以根据每个索引元素对应的根节点的结论可以知道,如果执行下面的操作

  • find(0)得到的结果为2
  • find(1)得到的结果为2
  • find(3)得到的结果为3

所以Quick Find的Find操作,时间复杂度为O(1)

查找的实现为

public int find(int v) {
    rangeCheck(v);
    return parents[v];
}
复制代码

所以,到这里,通过Quick Find的方式,就实现了并查集,不过,从合并的实现可以发现,在合并时,需要对所有元素进行一次遍历,所以合并的时间复杂度为O(n)。接下来,再来研究并查集的另外一种实现Quick Union

Quick Union- Union

前面说到,Quick Union的Find与Union时间复杂度都是O(logn),对比Quick Find中的Union时间复杂度O(n)来讲,性能提升很多,接下来就看以下,Quick Union是如何实现的。

首先最开始的步骤与Quick Find是一样的,都需要初始化,每一个元素属于一个单元素集合。即下列的5个元素

组成单元素集合后

初始化完成后,就开始利用Quick Union的思路执行Union操作。

执行union(1,0),现依然规定,左边的元素,跟随右边的元素,即这里合并后的话,是让左边元素的根节点,等于右边元素的根节点。即现在合并的1,0,其中1的根节点为1,0的根节点为0,由于左边元素的根节点等于右边元素的根节点,所以合并完成后,索引1的元素,根节点变为0,这一步,看起来和Quick Find没什么区别。

合并后的关系图如下

接下来,如果继续做union(1,2)操作的话,就有区别了。根据前面的结论,所以需要将索引1的根节点改为索引2的根节点。由于现在1的根节点为0,2的根节点为2,所以只需要让两个根节点来处理就好了,即让0与2进行连接就好了,最终就是索引为0的节点,父节点变为2。

合并后的关系图如下

继续执行union(4,1)操作,所以就是将4的根节点指向1的根节点,最终需要处理的节点就是4,2,达到的效果就是4指向2

合并后的关系图如下

再执行union(0,3),也就是说需要将0,3进行合并,仍然是找到0的根节点与3的根节点,然后将0根节点的父节点指向3的父节点即可

合并后的关系图如下

所以,最终看到的效果就是上图这样,这种操作对比之前Quick Find做的union操作就不一样了,Quick Find树的高度,最多就是2,但是采用Quick Union这种思路的话, 永远都是找到根节点进行操作,情况就不一样了,Quick Find是将左边集合中所有元素根节点,都改为右边元素的根节点,Quick只需要对左边元素的根节点进行操作即可

所以实现代码如下

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    parents[p1] = p2;
}
复制代码

接下来在研究Find操作是如何实现的

Quick Union - Find

首先,Find操作的目的是要返回当前集合的根节点,所以例如下图中的集合

对应的关系图如下

如果要查找1的根节点,就是从节点1开始,一直往上找,直到找到的节点,发现根节点是自己时,就说明已经找到根节点了,将该根节点进行返回即可。

所以

  • find(0)得到的结果为2
  • find(1)得到的结果为2
  • find(3)得到的结果为3

Find操作的时间复杂度我O(logn),由于Find的时间复杂度为O(logn),所以Union操作的时间复杂度也为O(logn)

Find的实现代码如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        v = parents[v];
    }
    return v;
}
复制代码

这样,Quick Union也实现了union与find操作。由于Quick Union与Quick Find之间时间复杂度的区别,所以建议使用性能更高的Quick Union。

Quick Union优化

在Union的过程中,可能会出现树不平衡的情况,甚至可能会退化成为链表,例如下图

如果现在要执行union(1,3),按照以前的操作,是将1的根节点,指向3的根节点,所以最终的结果如下

所以,如果一直按照这种方式进行合并的话,最终就真的会退化成为链表,一旦退化成为链表,最终find操作的时间复杂度就变为O(n),所以需要对前面的方案进行优化。

优化方案

  1. 基于size的优化:将元素少的树,嫁接到元素多的树
  2. 基于rank的优化:矮的树,嫁接到高的树
基于size的优化

例如有下图的两个集合,现在要将其合并

由于,现在是将元素少的树,嫁接到元素多的树上, 所以最终合并后的结果为

基于这种方式的实现,需要知道每个集合中有多少个元素,所以,要存储以下每个集合的size,由于在初始化时,全是单元素集合,所以在初始化时,也需要将size进行初始化,所以初始化的代码如下

public UnionFind_QuickUnion_Size(int capacity) {
    super(capacity);
    sizes = new int[capacity];
    for (int i = 0; i < sizes.length; i++) {
        sizes[i] = 1;
    }
}
复制代码

最终优化的部分,一定是合并集合的部分,所以只需要对union函数部分的代码进行优化就可以了

所以对size优化后的代码为

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    //size少的,嫁接到size多的上
    if (sizes[p1] > sizes[p2]) {
        parents[p2] = p1;//将p2嫁接到p1上
        sizes[p1] += sizes[p2];//更新size
    } else {
        parents[p1] = p2;
        sizes[p2] += sizes[p1];
    }
}
复制代码

然后现在对前面的几种实现,利用相同数量的元素进行对比,最终得到的结果如下

可以看到,基于size的优化,速度非常快,效果非常明显。

但是,基于size的优化,也可能存在树不平衡的问题。

例如需要将下图中的两个集合进行合并

如果是使用基于size的优化,最终合并的结果为

所以为了解决这种问题,将使用基于rank的优化

基于rank的优化

基于rank的优化,是不比较集合中的数量,而是比较集合中树的高度、基于树高进行优化的话,现在对下图中的两个集合进行合并,则是将树矮的树,合并到树高的树上

所以,最终是将根节点为4的树,嫁接上根节点为3的树上,最终合并完成后如下

很明显,这种优化,从树的平衡来讲,树会更加平衡,是由于基于size的优化的。

基于rank的优化,同样需要在初始化时,初始化每个单元素集合的高度进行初始化,所以初始化时的实现如下

private int[] ranks;
public UnionFind_QuickUnion_Rank(int capacity) {
    super(capacity);
    ranks = new int[capacity];
    for (int i = 0; i < ranks.length; i++) {
        ranks[i] = 1;
    }
}
复制代码

与基于size的优化相同,优化的部分也是在合并时,所以只需要对合并部分的代码进行优化即可。所以优化后的代码如下

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    //rank值小的,嫁接到rank值大的树上
    if (ranks[p1] > ranks[p2]) {
        parents[p2] = p1; //将矮的树,嫁接到高的树上
        //由于是矮的树嫁接到高的树上,所以不需要更新树高
    } else if (ranks[p1] < ranks[p2]){
        parents[p1] = p2;
    } else {
        //树高相等,进行合并,所以树高会增加1
        parents[p1] = p2;
        ranks[p2] += 1;
    }
}
复制代码

最终,将优化后的两种方案,用更大的测试数据进行测试后,得到的比较结果如下

可以发现,基于rank的优化,表现同样非常的优秀。不过需要注意,这并不意味着基于rank的优化性能低于基于size的优化,因为这两种优化,出发点不一样。基于rank的优化,主要是为了解决基于size优化中,出现不平衡的情况,建议使用基于rank的优化。

虽然两种优化,效果都非常好,不过仍然还有进一步的优化空间。接下来继续研究关于优化的问题

路径压缩(Path Compression)

什么叫路径压缩呢?比如说现在有如下的两个集合

现在基于Quick Union并且基于rank的优化,进行union(1,5)合并的话,得到的结果如下

合并后,可以发现,虽然有了基于rank的优化,树会相对平衡一点,但是,随着union的次数增加,树的高度依然会越来越高,最终导致find操作会变得越来越慢。所以,基于这样的问题的存在,可以进行路径压缩优化。

路径压缩

  • 在find时使路径上的所有节点都指向根节点,从而降低树的高度

这句话的意思就是说,执行完find操作以后,这条路径上的所有节点,都直接指向根节点,所以例如执行find(1)操作,执行完成后的结果如下图

可以发现,执行完find操作后,原来路径上的节点2,3,4都直接指向了根节点,通过这样的优化,树的高度仅进一步降低,所以如果继续执行find(0),find(7)操作,最终在find后,路径上的所有节点,都直接指向根节点,所以最终的结果如下

通过这样的优化后,以后在进行find操作时,就会变得非常快。而且由于union也要使用到find,所以最终union效率也会提升。所以,最终要达到的效果就是树越矮越好。接下来就研究,如何实现。

前面说到,路径压缩是对find进行优化,所以这次需要对find方法重新实现,最终find的实现如下

public int find(int v) {
    rangeCheck(v);
    if (v != parents[v]) {
        //修改v的父节点,通过递归调用,最终找到根节点,将v的父节点指向根节点
        //顺便将整条路径节点的父节点都修改为根节点
        parents[v] = find(parents[v]);
    }
    return parents[v];
}
复制代码

通过优化后,与size,rank优化进行对比,最终得到的结果如下

可以看到,最终的效果依然非常明显。但是依然有以下注意点

  1. 路径压缩使路径上的所有节点都指向根节点,所以实现成本稍高,例如有递归调用,会开辟更多的栈空间

所以,基于这种问题,还有另外2中更优的做法,不仅能降低树高,实现成本也会比路径压缩更低,分别为

  1. 路径分裂(Path Spliting)
  2. 路径减半(Path Halving)

路径分裂,路径减半的效率差不多,但都比路径压缩要好

路径分裂(Path Spliting)

路径分裂:使路径上的每个节点都指向其祖父节点(parent的parent)

例如,下列的集合

在执行find(1)操作时,会将1指向3,3指向5,5指向7,2指向4,4指向6,6指向7,所以最终执行完毕后的结果如下图

所以,可以看到,使用了路径分裂这种优化方案的话, 树的高度的确是降低了,不像路径压缩一样,直接将所有子节点平铺开。所以拆分的成本会比路径压缩低一些。所以基于这种思路,最终实现的代码如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        //将当前节点的父节点保存下来
        int p = parents[v];
        //然后让当前节点指向祖父节点
        parents[v] = parents[parents[v]];
        //更新节点,重复执行操作
        v = p;
    }
    return v;
}
复制代码

通过与前面几种优化方案进行对比,最终得到的比较结果如下

可以发现,路径分裂方案确实进一步优化了性能。说明这种路径分裂方案是可行的,那接下来再研究路径减半这种优化方案。

路径减半(Path Halving)

路径减半:使路径上的每隔一个节点就指向其祖父节点(parent的parent)

对比前面的路径分裂,路径分裂是每一个节点,都指向祖父节点,路径减半是每隔一个节点就指向祖父节点。那究竟是什么意思呢?例如有下图的集合

现在执行find(1)操作,根据上面的定义,即执行完find(1)后,1指向祖父节点,3指向祖父节点,5指向祖父节点,即3指向5,5指向7,其余元素保持不变,所以最终的结果如下图

其实可以发现,这种方案对比前面的路径分裂,效果类似。因为最红优化后的树高,是一样的。现在已经知道了优化办法,根据这种优化办法,最终得到的优化代码如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        //然后让当前节点指向祖父节点
        parents[v] = parents[parents[v]];
        //parents[v]为祖父节点,祖父节点重复执行操作
        v = parents[v];
    }
    return v;
}
复制代码

最终通过下图几种优化方案的对不,可以发现,路径减半和路径分裂的性能很接近

理论上来讲,路径减半与路径分裂两种算法,都非常优秀。并且总体来讲,都要由于其他优化方案。

总结

摘自《维基百科》:en.wikipedia.org/wiki/Disjoi…

大概意思是

  1. 使用路径压缩,分裂或者减半 + 基于rank或者size的优化
    • 可以确保每个操作的均摊时间复杂度为O(α(n)),α(n) < 5

个人建议的搭配

  1. Quick Union
  2. 基于rank的优化
  3. Path Halving或者Path Spliting

自定义类型

之前的使用都是基于整型数据,如果其他自定义类型也想使用并查集,如何实现呢?可以参考以下方案

  1. 通过一些方法,将自定义类型转换为整型后,使用并查集(比如生成哈希值)
  2. 使用链表+映射(Map)

为什么可以使用链表实现呢?因为并查集本质上就是树形结构,只不过是通过数组来表达这种树形结构。然后树形结构中的每一条分支,都是一条链表。

demo下载地址

完!

关注下面的标签,发现更多相似文章
评论