【并查集】一种简单而强大高效的数据结构
目录
一、并查集原理
并查集（Disjoint Set）是一种用来管理元素分组和查找元素所属组别的数据结构。它主要支持两种操作：查找（Find）和合并（Union）。
在并查集中，每个元素都被分配一个代表元素（也可以称为根节点），该代表元素用来表示所属的组别。初始时，每个元素都是其自身的代表元素，即根节点。当需要进行合并操作时，实际上是将两个组别的根节点连接在一起，从而将这两个组别合并为一个组别。而查找操作则是通过不断向上查找代表元素，直到找到根节点为止，以确定元素所属的组别。
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。
此时将这三个集合用一个数组表示：
从上图可以看出：编号6,7,8同学属于0号小分队，该小分队中有4人(包含队长0)；编号为4和9的同学属于1号小分队，该小分队有3人(包含队长1)，编号为3和5的同学属于2号小分队，该小分队有3个人(包含队长1)。
- 数组的下标对应集合中元素的编号
- 数组中如果为负数，负号代表根，数字代表该集合中元素个数
- 数组中如果为非负数，代表该元素双亲在数组中的下标
一段时间后，假设s1小分队的8号元素和s2小分队的1号元素玩到了一起，两个小圈子相互介绍认识，最后成为了一个小圈子，这就是合并。
二、并查集实现
- 1. 查找元素属于哪个集合
- 沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
- 2. 查看两个元素是否属于同一个集合
- 沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
- 3. 将两个集合归并成一个集合
- 将两个集合中的元素合并
- 将一个集合名称改成另一个集合的名称
- 4. 集合的个数
- 遍历数组，数组中元素为负数的个数即为集合的个数。
到此可以看到，并查集并不复杂。综上，就能够自己实现一个并查集：
import java.util.Arrays;
public class UnionFindSet {
public int[] elem;
public UnionFindSet(int n) {
this.elem = new int[n];
Arrays.fill(elem, -1);
}
/**
* 找x下标对应的根
*
* @param x 下标
* @return x根的下标
*/
public int findRoot(int x) {
if (x < 0) {
throw new IndexOutOfBoundsException("下标不合法");
}
while (elem[x] >= 0) {
x = elem[x];
}
return x;
}
/**
* 合并两个集合 x1和x2必须从根合并
*
* @param x1 把x2作为自己的子集
* @param x2 成为x1的子集
*/
public void union(int x1, int x2) {
//x1和x2到自己集合的根位置
x1 = findRoot(x1);
x2 = findRoot(x2);
if (x1 == x2) return; //相同根，不需要合并
elem[x1] = elem[x1] + elem[x2];
elem[x2] = x1;
}
/**
* 判断两个下标对应的数字是否在一个集合中 -> 是否同根
*/
public boolean isSameSet(int x1, int x2) {
x1 = findRoot(x1);
x2 = findRoot(x2);
return x1 == x2;
}
/**
* 求数组中集合的个数
*/
public int getCount() {
int count = 0;
for (int x : elem) {
if (x < 0) {
count++;
}
}
return count;
}
}UnionFindSet类测试：
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
UnionFindSet ufs = new UnionFindSet(10);
ufs.union(0, 6);
ufs.union(0, 7);
ufs.union(0, 8);
ufs.union(1, 4);
ufs.union(1, 9);
ufs.union(2, 3);
ufs.union(2, 5);
System.out.println(Arrays.toString(ufs.elem));
System.out.println("合并根为0和根为1的集合:");
ufs.union(0, 1);
System.out.println(Arrays.toString(ufs.elem));
System.out.println(ufs.isSameSet(3, 6));
System.out.println(ufs.isSameSet(4, 8));
System.out.println(ufs.getCount());
}
} 测试结果正确：
三、并查集应用
1. LeetCode并查集相关OJ题
题目一：LeetCdoe 547. 省份数量
https://leetcode.cn/problems/number-of-provinces/description/
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
思路：前面我们已经自己实现了一个并查集，这里就可以用上。题目说到：
isConnected[i][j] = 1表示第i个城市和第j个城市直接相连，而isConnected[i][j] = 0表示二者不直接相连。对于矩阵中值为1的元素，将他们所对应城市相连，进行合并（i ==j时就是自己和自己相连，不需要合并），最后看并查集中负数的个数，即为省份数量。
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
UnionFindSet ufs = new UnionFindSet(n);
//遍历数组，合并
for(int i = 0; i < n; i++) {
for(int j = 0; j < isConnected[i].length; j++) {
if(i != j && isConnected[i][j] == 1) {
ufs.union(i, j);
}
}
}
return ufs.getCount();
}
}前面自己实现的并查集类也要放到代码框中，官方题解中同样有并查集的解法。
题目2：LeetCode 990. 等式方程的可满足性https://leetcode.cn/problems/satisfiability-of-equality-equations/
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
思路：将每个变量看出一个节点，==关系看作两者的连接，即将两者合并成一个集合（题目的提示：出现的字母都为小写字母，因此集合的长度给26就够了）。我们先遍历一次数组，将所有==关系的变量合并；再遍历数组，看每个 != 关系的两个变量是否在同一个集合中，如果在同一个集合，说明与方程冲突，即为false。若都无冲突，即为true。
class Solution {
public boolean equationsPossible(String[] equations) {
//1.合并所有==的情况
int n = equations.length;
UnionFindSet ufs = new UnionFindSet(26);//所有小写字母
for(int i = 0; i < n; i++) {
if(equations[i].charAt(1) == '=') {
//合并
ufs.union(equations[i].charAt(0) - 'a',equations[i].charAt(3) - 'a');
}
}
//2.判断!=的情况是否正确
for(int i = 0; i < n; i++) {
//如果==，说明不满足方程
if(equations[i].charAt(1) == '!' &&
ufs.isSameSet(equations[i].charAt(0) - 'a',equations[i].charAt(3) - 'a')) {
return false;
}
}
return true;
}
}同样，前面自己实现的并查集类也要放到代码框中，官方题解中也是并查集的解法。
2. 并查集的其他应用及总结
并查集还有一些其他的应用：
-
连通性问题：并查集常被用来判断图中节点之间的连通性。通过并查集可以快速判断两个节点是否在同一个连通分量中，从而进行相关操作，比如最小生成树算法中的 Kruskal 算法。
-
图论中的环检测：在无向图中，可以利用并查集来检测是否存在环路。每次加入一条边时，如果边的两个端点已经在同一个连通分量中，则说明存在环路。
-
最近公共祖先（LCA）问题：在树形结构中，通过并查集可以快速计算两个节点的最近公共祖先。
-
社交网络中的关系处理：在社交网络中，可以利用并查集维护用户之间的关系，快速合并用户的关系圈子或者查找两个用户之间的关系。
总结：并查集在算法和数据结构领域有着广泛的应用，其时间复杂度通常为接近常数级别，使其成为许多算法和数据结构中重要的一部分。虽然并查集很优秀，但相对来说并查集面试的频率不是特别高，可以说不是一个面试热点。虽然如此，并查集的思想还是很实用的，是一个很有意思的数据结构，通常一旦想到用并查集解决问题，思路也会变得很清晰，所以建议还是好好学习一下。
原文地址：https://blog.csdn.net/sjsjzhx/article/details/136479764
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！