并查集(一)并查集的几种实现

概述

并查集是一种特别的数据结构,在解决连通行问题屡试不爽。以下代码均为java语言的实现

并查集的作用先总体说一下

  • 1、将两个元素联通起来(union)起来,形成一个通路
  • 2、检查任意两个元素是否是连通的
  • 3、连通后,如果把连通的一组数看成一组,那么还能记录一共有多少组数
  • 4、当然也还能求组员数最大、最小的组的数量【通过计数变形】

对外基础方法提供2个方法

  • public void join(int a, int b) 连通a节点和b节点
  • public boolean isJoined(int a, int b) 判断任意两个节点是否是连通的

内部需要一个辅助方法

来查询任意节点的根节点,本身你可以理解并查集是一颗树,但这颗是反向寻找,并不是像通常的树,自顶向下dfs的,而是一直向上找寻根节点

  • private int findP(int x) 查询x元素的根节点

快速查询版本

将连通节点的父节点都设置为相同节点(索引),查询的时候 f(x)=parent[x],但更新比较麻烦,每次更新需要遍历所有元素O(n)的复杂度,n是总的元素个数

/**
 * 并查集  快速查询
 */
public class UFQuickFind {

    int[] parent;

    public UFQuickFind(int size) {
        parent = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }


    private int findP(int x) {//查询操作,其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        return parent[x];   //直接返回 parent就可以了,因为所有  连接 的节点parent值都相同
    }

    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            for (int i = 0; i < parent.length; i++) {
                if (parent[i] == ap)
                    parent[i] = bp; //修改成相同的 parent
            }
        }
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }


}

快速合并版

合并的时候,a,b元素,直接让将a的父亲指向b的父亲。【通俗一点 a节点的父亲 认b节点的根节点做父亲了,最后a节点tm的就程b节点的根节点的孙子了】

/**
 * 快速合并
 */
public class UFQuickUnion {

    int[] parent;

    public UFQuickUnion(int size) {
        parent = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }

    private int findP(int x) {//查询操作,其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != x)//一直搜索到根节点
            x = parent[x];

        return x;
    }

    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            parent[ap] = bp;//让其中一个节点的根节点 指向  另外一个节点的根节点
        }
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }

}

基于每株节点数的合并

由于快速合并的过程,合并的过程是随机的,如果所有节点都合并到一起,那么最后这颗树可能变成一个链表【就是接龙,成为一条线】,通过节点数来改进,节点数少的接到节点数多的上面,这样肯定不会成一个链表

public class UFNumsUnion {


    int[] parent;
    int[] nums;//节点数

    public UFNumsUnion(int size) {
        parent = new int[size];
        nums = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            nums[i] = 1;
        }
    }

    private int findP(int x) {//查询操作,其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != x)//一直搜索到根节点
            x = parent[x];

        return x;
    }

    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            //a节点多,就将 b节点往a节点上合并,这样的话可以减少树的高度
            if (nums[ap] > nums[bp]) {
                parent[bp] = ap;
                nums[ap] += nums[bp];    //根节点的节点数  增加了  被合并节点的节点数
            } else {
                parent[ap] = bp;
                nums[bp] += nums[ap];
            }
        }
    }


    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }

}

基于层数的实现

【基于每株节点数的合并】虽然已经挺好的了,但偶尔也会不太合理的情况如下所示


   A:      o
        / | \        o  o  o o        5个节点,两层
      
  
   B:    o
       / | 
      o  o              4个节点  3层
     /
    o 

上面这种情况按照基于节点数的合并,会得到一个4层的树(层的深度增加),而更合理的方式是让A接到B上,这样最后整体层数保持在3层。层数越小,那么findP方法就会变快,而合并也因为调用findP方法也会加快。

基于层数的实现,永远让层数矮的接到层数高的树上

public class UFRankUnion {

    int[] parent;
    int[] rank;//树的层数
    int plant;  //一共有多少株树

    public UFRankUnion(int size) {
        plant = size;
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }


    private int findP(int x) {//查询操作,其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != x)//一直搜索到根节点
            x = parent[x];

        return x;
    }


    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            plant--;
            //a的层数越高,就将层数少的合并到层数高的上面
            if (rank[ap] > rank[bp])
                parent[bp] = ap;
            else if (rank[ap] < rank[bp]) {
                parent[ap] = bp;
            } else {
                //相同情况的话,随便就可以,但总体层高会增加1,画一个相同层的树合并一下就知道
                parent[ap] = bp;
                rank[bp]++;
            }
        }
    }

    public int getPlant() {
        return plant;
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }


}

路径压缩

我们设想一下并查集的理想状态,所有树都是深度为1的树,这种理想状况的findP的时间复杂度为O(1),大大提高了查询性能,如下图所示

           o             o
        / | \ \        / | \ 
       o  o  o o      o  o  o
       
     
       所有的树都是以这种方式去组合的

但是我们知道,如果A和B合并,层高是不是又变成2层了,如何才能让层高再次恢复到1层呢。这里路径压缩的一种方式是在查询的时候,将查询的节点不断往上提高,直接接到根节点上

      节点1  o         
           / | \       
   节点2  o  o  o
         /
 节点3  o 节点1

查询节点3的时候,是不是让节点3接到 节点2的父节点上 parent[节点3]= parent[节点2]

public class UFRankUnionCompressPath {


    int[] parent;
    int[] rank;//树的层数
    int plant;  //一共有多少株树

    public UFRankUnionCompressPath(int size) {
        plant = size;
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    private int findP(int x) {//查询操作,其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != parent[parent[x]])
        //如果parent[x]==parent[parent[x]] 说明这颗树到了第二层,或者第一层
        //第一层 因为parent[x]=x所以有  parent[x]==parent[parent[x]]
        //第二层 因为第二层的parent是根节点 有: parent[x]= root  
        //所以有 parent[parent[x]]= parent[root]  而本身 parent[root]=root
        {
            // x = parent[x];  //
            parent[x] = parent[parent[x]]; //将下层节点往顶层提升,最终
        }
        return parent[x];
    }


    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            plant--;
            //a的层数越高,就将层数少的合并到层数高的上面
            if (rank[ap] > rank[bp])
                parent[bp] = ap;
            else if (rank[ap] < rank[bp]) {
                parent[ap] = bp;
            } else {
                //相同情况的话,随便就可以
                parent[ap] = bp;
                rank[bp]++;
            }
        }
    }

    public int getPlant() {
        return plant;
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }
}

期待下一篇,并查集运用相关得算法题及题解

并查集(一)并查集的几种实现

上一篇:第三章 线性回归


下一篇:布隆过滤器