算法原理系列:并查集

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72830661

算法原理系列:并查集

《算法》当中第一章节就介绍了该数据结构,但并不知道它到底有何用,也就一直没有研究它。当做过一系列数组+链表+树的题目之后,再看看这并查集似乎又有点意思了,今天就探寻下。

介绍

我对并查集的具体应用还不了解,所以就从一些基本的题目引出并查集。

并查含义:合并集合,查找集合。

可以有的操作如下:

  • 给定两个“结点”,检查它们是否同属一个集合。(在同一集合中,所有元素均同质,因此判断两个元素是否属同集合是分类分组的前提。)
  • 给定两个“结点”,把它们归并到同一集合中。(所以说,这些集合都有些共同特性,才能归在一起吧)
  • 给定某个“结点”,判断它属哪个集合。(如果集合有唯一标识的话,我们可以实现该操作)

所以基本的并查集API如下:

public class UF {

    int[] union;

    public UF(int N) {
        union = new int[N];
        for (int i = 0; i < N; i++){
            union[i] = i;
        }
    }

    public void union(int p, int q){
    }

    public int find(int p){
        return 0;
    }

    public boolean connected(int p, int q){
        return false;
    }

    public int count(){
        return 0;
    }

    public static void main(String[] args) {
        In in = new In("./data/tinyUF.txt");
        int N = in.readInt();
        UF uf = new UF(N);
        for (int i = 0; i < N; i++){
            int p = in.readInt();
            int q = in.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p,q);
            System.out.println(p + " " + q);
        }
        System.out.println(uf.count() + " components");
    }

}

union的数据结构采用数组形式,数组有两个天然的标识:index和value,所以在并查集应用中,由于index均唯一,所以它们可以代表每一个元素,而value则可以表示集合。

实现一(quick-find)

既然,我们能够对数组中的每个value进行操作,且初始化时,所有元素都有一个唯一的集合。union[i] = i,那么我们就用这唯一的i作为集合标识。比如:当需要连接p和q时,我们进行如下操作:

union[q] = q -> union[q] = p;

此时集合p中的元素有<p,q>

所以,后续一旦有新的元素要加入到集合p中,如union(x,y)
int id = find(x);
union[y] = id;

代码如下:

public class UF {

    int[] union;
    int SIZE;

    public UF(int N) {
        union = new int[N];
        for (int i = 0; i < N; i++){
            union[i] = i;
        }
        SIZE = N;
    }

    public void union(int p, int q){
        int x = find(p);
        int y = find(q);

        if (x == y) return;

        for (int i = 0; i < union.length; i++){
            if (union[i] == y) union[i] = x;
        }

        SIZE --;
    }

    public int find(int p){
        return union[p];
    }

    public boolean connected(int p, int q){
        return find(p) == find(q);
    }

    public int count(){
        return SIZE;
    }

    public static void main(String[] args) {
        In in = new In("./data/tinyUF.txt");
        int N = in.readInt();
        UF uf = new UF(N);
        for (int i = 0; i < N; i++){
            int p = in.readInt();
            int q = in.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p,q);
            System.out.println(p + " " + q);
        }
        System.out.println(uf.count() + " components");
    }
}

关键在于union中的代码,为了维护元素所属的集合,在合并集合时:

p集合 <p1,p2>
q集合 <q1,q2,q3,q4,q5,a6>

union(p2,q1)操作
需要更新q集合中的每个元素,把它们对应的值改为p。

在代码实现中更加糟糕,需要遍历整个数组一次,所以:

union操作复杂度:O(n)
find操作复杂度: O(1)

一种基于数组的扁平结构,虽然find非常快,但对于合并操作真的是太糟糕了,可不可以加快合并?

实现二(quick-union)

在union操作中,为了维护这种扁平结构,需要循环遍历一次数组,这种操作相当费时。熟悉树的话,我们知道,对两棵树的合并相当简单,只要把一棵树依附到某个结点上,就能合并成一棵更大的树。

而对于任何子结点而言,如果我们能追根溯源到根结点,那么就认为这些结点都属于同一棵树,这意义巨大,同一棵树我们即可表示为同一集合,因为任何结点在这棵树中的归属一致。(通过find手段找到同根)

所以quick-union的合并思路和树的合并一个道理,union(p,q),p和q可以分别表示在存在于某棵树的两个中间结点,找到它们的根结点后,把一棵根结点树并到另一个根结点的孩子上。

嗯,数组可以用来表示森林,在堆中我们还知道数组可以表示成严格的完全二叉树。可见数组不仅仅是数组啊!

代码如下:

public void union(int p, int q){
        int pid = find(p);
        int qid = find(q);

        if (pid == qid) return;

        union[qid] = pid;

        SIZE--;
    }

    public int find(int p){
        while (p != union[p]){
            p = union[p];
        }
        return p;
    }

在平均情况下,union操作和find操作已经相当不错了,起码它们的时间复杂度为树的高度。可以参看《算法》P147页的时间复杂度分析。

但森林的构建非常依赖于输入union操作的顺序,在最坏情况下,可能会出现深度为N的一棵树,此时它的find操作就退化成了O(n)O(n),而union依赖find,也成了O(n)O(n),与其这样还不如再做点优化,稳定树的生长深度。

实现三(加权quick-union)

在最坏情况下,quick-union的深度即为结点数。这是因为在合并操作时,总是把大树依附在小树的结点上。所以为了规避上述这种情况,一种可行的方案就是把当遇到大树依附小树的情况,进行反向操作,让小树依附在大树上。

代码如下:

public class WeightedQuickUnionUF {

    int[] id;
    int[] sz;
    int count;

    public WeightedQuickUnionUF(int N){
        count = N;
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
        for (int i = 0; i < N; i++) sz[i] = 1;
    }

    public void union(int p, int q){
        int pid = find(p);
        int qid = find(q);

        if (pid == qid) return;

        if (sz[pid] < sz[qid]){
            id[pid] = qid;
            sz[qid] += sz[pid];
        }
        else{
            id[qid] = pid;
            sz[pid] += sz[qid];
        }
        count --;
    }

    public boolean connect(int p, int q){
        return find(p) == find(q);
    }

    public int find(int p){
        while (p != id[p]){
            p = id[p];
        }
        return p;
    }

    public int count(){
        return count;
    }

    public static void main(String[] args) {
        In in = new In("./data/largeUF.txt");
        int N = in.readInt();
        UF uf = new UF(N);
        for (int i = 0; i < N; i++){
            int p = in.readInt();
            int q = in.readInt();
            if (uf.connected(p, q)) continue;
            uf.union(p,q);
            //System.out.println(p + " " + q);
        }
        System.out.println(uf.count() + " components");
    }

}

一开始我以为sz是用来记录当前集合的高度,但不然,它记录的是当前集合的个数。这点很神奇,当把集合个数小的(小树)合并到集合个数大的大树上时,它就能规避最坏的情况。

对我来说有两点疑问:

  • 集合个数和树的高度是否等价?
  • 为什么把小树合并到大树上就能保证最坏情况不会出现,如何证明?

要回答第一个问题,先得解决第二个问题,第二个问题比较简单。出现最坏情况的原因在于每当进行union操作时,树的深度就+1,树深度+1何时会出现?当且仅当大树依附在小树上,此时树的深度一定更新为1+大树深度,因为小树深度<大树深度,所以合并操作导致树的高度变大。

我们的目标是尽量维持树的深度,如小树树高为3,大树树该为5,那么我们可以让小树依附在大树上,此时整棵树的高度没有增加依旧为5。

那为什么用元素个数来衡量树高同样可以保证算法正确呢? 归纳假设,在初始时,所有结点自成一派,元素个数为1,高度也为1,保证了find的高效性。

假设size小的集合,树的高度也较小,那么进行一轮合并得到新的集合时,高度不会增加。所以只要按照这种顺序更新,即能规避最坏情况。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券