Java—并查集_java 并查集

Java—并查集

一、基本概念

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想：用一个数组表示了整片森林（parent），树的根节点唯一标识一个集合，只要找到了某个元素的的树根，就能确它在哪个集合里。

示例：

假设一个团体有10个人，将这些人编号为0到9，然后用数组a[i]的下标i表示这些人的编号，数组元素a[i]初始存储的全是-1

查找

数组中存储的数据则代表他们之间的关联方式

例如0，6，7，8互相认识，那么他们就是一个集合，而0号是这个集合中的老大，那么0下标就存储这个团体的人的个数的相反数：-4，其他的几个成员6，7，8，则分别存储他们认识的0的下标：0

如果我们还有另两个集合，例如1，4，9是一个集合，1是老大，4和9存储1的下标，那么4和9存储1，1下标存储-3，而2，3，5是另一个集合，2是老大，则3，5存储2下标，2存储-3

合并

当的集合1和集合2的某一位互相认识，那么根据传递原理，集合1和集合2就都互相认识了，那么就会变成一个更大的集合，其中如果让0做老大，1隶属于0下标，那么就会形成下面的样子

0下标就存储了这个大集合的人数的相反数：-7，而1则从老大变成了平民，因此存储老大的下标：0，其他的都是不变的

二、应用场景

并查集用在一些有 N 个元素的集合元素查找和集合合并应用问题中，一般N的数据量极大

三、具体实现

变量和构造方法

我们的底层数据结构是数组，在创建的时候，需要给数组传递一个创建的大小，并且用Arrays.fill方法，将数组的全部元素置为-1

public int[] elem;

public MyUnionFindSet(int n){
    this.elem = new int[n];
    Arrays.fill(elem, -1);//初始化数组全为-1
}
1
2
3
4
5
6

寻找根节点

这个方法就是用来找集合中的老大-根节点

通过之前的介绍，只有父节点存储的是负数，而其他下标则存储其父节点的下标。所以可以用一个循环，当这个下标对应的数据不是负数，那么就让x变为这个下标对应的数据，直到找到负数，就返回这个x

例如我们这个图中，如果我们传递的参数是9，那么elem[9]是1，那么x就变成1，elem[1]是0，那么x就变成0，elem[0]是-7,所以0是根节

点，返回0

/**
 * 查找x下标数据的根节点
 * @param x
 * @return 根节点的下标
 */
public int findRoot(int x){
    if(x < 0){
        throw new ArrayIndexOutOfBoundsException("下标不能是负数");
    }

    while(elem[x] >= 0){
        x = elem[x];
    }
    return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

判断两节点是否在同一个集合

当两个节点在同一个集合中，说明他们的根节点一定是相通的，所以我们可以调用findRoot方法，来找到两个节点的根节点，判断是否相

同，相同返回true，不同返回false

/**
 * 查询x1和x2是否在同一个集合中
 * @param x1
 * @param x2
 * @return
 */
public boolean isSameUnionFindSet(int x1, int x2){
    int index1 = findRoot(x1);
    int index2 = findRoot(x2);

    if(index1 == index2){
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

合并两个集合

通过刚才的图片我们可以知道，当两个节点相连时，如果这两个节点不是根节点，那么就应该找到这两个节点的根节点，如果根节点相同，说明这两个节点已经在同一个集合中了，那么就不用合并了。而如果根节点不相同，那么就和刚才讲的情形类似，就是把0和1相连，这时改变的只有0下标的值和1下标的值，其他的下标的值都是不变的

可以看到，0下标的值变成了两个集合的节点数目的总和的相反数，也就是0下标的值加上1下标的值：-7，而1下标的值则是直接改为了0

所以，可以先找到x1，x2的根节点，判断是否相等，相等则直接返回。这里实现的逻辑x1是0，x2是1，所以

elem[0] = elem[0] + elem[1]
elem[1] = 0
1
2

也就是：

elem[index1] = elem[index1] + elem[index2]
elem[index2] = index1
1
2

完整代码如下：

/**
 * 合并x1,x2所在的两个集合
 * @param x1
 * @param x2
 */
public void union(int x1, int x2){
   int index1 = findRoot(x1);
   int index2 = findRoot(x2);

   if(index1 == index2){
       System.out.println("x1和x2已经在同一个集合中了");
       return;
   }

   elem[index1] = elem[index1] + elem[index2];
   elem[index2] = index1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

获取集合的个数

可以看到，集合的个数等于所有老大的个数，等于数组中负数的个数

public int getCount(){
    int count = 0;
    for (int x:elem) {
        if(x < 0){
            count++;
        }
    }
    return count;
}

1
2
3
4
5
6
7
8
9
10

四、测试

打印

public void print(){
    for (int x:elem) {
        System.out.print(x + " ");
    }
    System.out.println();
}
1
2
3
4
5
6

测试

public static void main(String[] args) {
    MyUnionFindSet myUnionFindSet = new MyUnionFindSet(10);
    System.out.println("合并0和6");
    myUnionFindSet.union(0,6);
    System.out.println("合并0和7");
    myUnionFindSet.union(0,7);
    System.out.println("合并0和8");
    myUnionFindSet.union(0,8);

    System.out.println("合并1和4");
    myUnionFindSet.union(1,4);
    System.out.println("合并1和9");
    myUnionFindSet.union(1,9);
    System.out.println("合并2和3");
    myUnionFindSet.union(2,3);
    System.out.println("合并2和5");
    myUnionFindSet.union(2,5);

    myUnionFindSet.print();

    System.out.println("合并8和1");
    myUnionFindSet.union(8,1);

    myUnionFindSet.print();

    System.out.println("查找是否为同一个集合");
    System.out.println(myUnionFindSet.isSameUnionFindSet(6,9));
    System.out.println(myUnionFindSet.isSameUnionFindSet(8,2));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

五、并查集优化

问题

特别情况下（集合元素较多）树的高度可能会比较高，查询性能劣化—find(x)的复杂度将为常数级

例如上述{1, 2, 3, 5}这个集合，连续地与单节点集合{6}, {7}, {8}执行union(6, 5), union(7, 5), union(8, 5)之后，将得到如下。

解决办法：树的高度降低

方案一：按大小求并

若一棵树拥有越多的节点，其高度倾向于越高。因此在合并前先比较两棵树的大小，将较小树的根连接到较大树的根以完成合并。

如下代码在构造方法中初始化树大小数组size[]。

public int[] elem;
private int[] size; // 保存树的大小

public MyUnionFindSet(int n){
    this.elem = new int[n];
    this.size = new int[n];
    Arrays.fill(elem, -1); // 初始化数组全为-1
    Arrays.fill(size, 1); // 初始化数组全为1
}
1
2
3
4
5
6
7
8
9

按大小求并。

/**
 * 合并x1,x2所在的两个集合
 * @param x1
 * @param x2
 */
public void union(int x1, int x2){
   int index1 = findRoot(x1);
   int index2 = findRoot(x2);

   if(index1 == index2){
       System.out.println("x1和x2已经在同一个集合中了");
       return;
   }
    // 根节点不同才求并
   if(elem[index1] <= elem[index2]){
       elem[index1] = elem[index1] + elem[index2];
       elem[index2] = index1;
   } else {
       elem[index2] = elem[index1] + elem[index2];
       elem[index1] = index2;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方案二：按秩(高度)求并

**问题：**一棵大小较小的树反而高于较大的树，直接按高度求并比按大小求并能更准确地使每次合并后的新树高度较小。

另外，不同于按大小求并时每次合并均修改新树的大小信息，按高度求并时，新树的高度变化只发生在两棵树高度相等时，此时高度加1。

public int[] elem;
private int[] rank; // 保存树的大小

public MyUnionFindSet(int n){
    this.elem = new int[n];
    this.rank = new int[n];
    Arrays.fill(elem, -1); // 初始化数组全为-1
    Arrays.fill(rank, 1); // 初始化数组全为1
}
1
2
3
4
5
6
7
8
9

按秩(高度)求并

/**
 * 合并x1,x2所在的两个集合
 * @param x1
 * @param x2
 */
public void union(int x1, int x2){
   int index1 = findRoot(x1);
   int index2 = findRoot(x2);

   if(index1 == index2){
       System.out.println("x1和x2已经在同一个集合中了");
       return;
   }
    // 根节点不同才求并
   if(elem[index1] <= elem[index2]){
       elem[index1] = (elem[index1] > 0 ? elem[index1] : 1) + 1;
       elem[index2] = index1;
   } else {
       elem[index2] = (elem[index2] > 0 ? elem[index2] : 1) + 1;
       elem[index1] = index2;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

对前述{1, 2, 3, 5}集合，连续地与单节点集合{6}, {7}, {8}执行union(6, 5), union(7, 5), union(8, 5)，在应用按秩求并之后，将得到如下。

六、并查集实际应用

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

解答：

https://leetcode.cn/problems/number-of-provinces/solution/li-kou-547-bing-cha-ji-si-lu-jiang-jie-b-u9qh/