并查集
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长7分钟
并查集是一种维护集合的数据结构，用于处理一些不相交集合的合并及查询问题，主要有查找和合并两种操作。
看一个具体的问题，已知一系列关于变量的等式，比如a==b, b==c, ...，问你其中两个变量是否相等，比如a和c是否相等？
示例1：
已知 a==b, b==c，问a==c是否成立?
示例2:
已知 a==b, c==d, b==e, e==c，问a==c是否成立？
思路是维护多个分组，将相等的变量划分到同一组，判断两个变量是否相等，只需要看他们是否属于同一个组。
问题是如何去维护这个分组？遍历等式时，首先需要查询等式两边的变量是否属于同一个分组，这就需要去查询所有的分组，看看两个变量是否属于同一个分组，有下面两种情况
- 左右两边的变量目前已经属于同一个分组，不用处理。
- 左右两边的变量目前属于不同的分组，需要将这两个分组合并。
上面提到的查询分组，还有合并分组，如果不使用并查集，操作起来就比较麻烦，而且效率低下，下面看看代码实现。
1import java.util.ArrayList;
2import java.util.HashSet;
3import java.util.List;
4import java.util.Set;
5
6public class Main {
7
8 public static void main(String[] args) {
9 List<String> equationList = new ArrayList<>();
10 equationList.add("a==b");
11 equationList.add("c==d");
12 equationList.add("b==e");
13 equationList.add("e==c");
14 System.out.println(isEquals(equationList, "a==c"));
15 }
16
17 public static boolean isEquals(List<String> equationList, String equation) {
18 List<Set<String>> groupList = new ArrayList<>();
19 for (String e : equationList) {
20 String[] vars = e.split("==");
21 Set<String> group1 = null, group2 = null;
22 /**
23 * 遍历所有分组，查找是否已经有分组包含变量
24 */
25 for (Set<String> group : groupList) {
26 if (group.contains(vars[0])) {
27 group1 = group;
28 }
29 if (group.contains(vars[1])) {
30 group2 = group;
31 }
32 if (group1 != null && group2 != null) {
33 break;
34 }
35 }
36
37 if (group1 == null && group2 == null) {
38 /**
39 * 如果当前所有分组不包含两个变量，则创建一个新的分组
40 */
41 group1 = new HashSet<>();
42 group1.add(vars[0]);
43 group1.add(vars[1]);
44 groupList.add(group1);
45 } else if (group1 != null && group2 == null) {
46 /**
47 * 如果已经有分组包含第一个变量，则将第二个变量添加到该分组
48 */
49 group1.add(vars[1]);
50 } else if (group1 == null && group2 != null) {
51 /**
52 * 如果已经有分组包含第二个变量，则将第一个变量添加到该分组
53 */
54 group2.add(vars[0]);
55 } else if (group1 != null && group2 != null && group1 != group2) {
56 /***
57 * 如果已经有分组包含两个变量，且两个变量不在同一个分组，则合并这两个分组
58 */
59 group1.addAll(group2);
60 groupList.remove(group2);
61 }
62 }
63 String[] vars = equation.split("==");
64 for (Set<String> group : groupList) {
65 if (group.contains(vars[0]) && group.contains(vars[1])) {
66 return true;
67 }
68 }
69 return false;
70 }
71}
72注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
并查集就是为了简化多个集合查询和合并的，并查集是通过指向来维护集合，如果最终指向相同则说明他们属于同一个集合，最后一个元素指向自身，比如
- a->b或者b->a，说明a和b是属于同一个集合。
- c->d->e、c->e->d、d->c->e、....，说明c、d和e属于同一个集合。
如果要合并这两个集合a->b和c->d->e，只需要将b指向e即可，如下图
上述的问题用并查集实现，代码如下
最小生成树kruskal算法中应用了并查集算法，具体可查看课程最小生成树之Kruskal算法
注释1import java.util.*;
2
3class UnionFind {
4
5 private final Map<String, String> map = new HashMap<>();
6
7 public String find(String var) {
8 while (!Objects.equals(map.getOrDefault(var, var), var)) {
9 var = map.get(var);
10 }
11 return var;
12 }
13
14 public void union(String var1, String var2) {
15 String root1 = find(var1);
16 String root2 = find(var2);
17 if (!Objects.equals(root1, root2)) {
18 map.put(root1, root2);
19 }
20 }
21}
22
23public class Main {
24
25 public static void main(String[] args) {
26 List<String> equationList = new ArrayList<>();
27 equationList.add("a==b");
28 equationList.add("c==d");
29 equationList.add("b==e");
30 equationList.add("e==c");
31 System.out.println(isEquals(equationList, "a==c"));
32 }
33
34 public static boolean isEquals(List<String> equationList, String equation) {
35 UnionFind unionFind = new UnionFind();
36 for (String e : equationList) {
37 String[] vars = e.split("==");
38 unionFind.union(vars[0], vars[1]);
39 }
40 String[] vars = equation.split("==");
41 return Objects.equals(unionFind.find(vars[0]), unionFind.find(vars[1]));
42 }
43}注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
上面代码实现了并查集功能，但是并未做优化处理，在合并两个集合时，一般需要考虑将层级较少的根元素指向层级较多的根元素。比如上面两个集合a->b和c->d->e，一般我们会让b指向e，而不是让e指向b，因为这样可以减少合并后整体的层级。
并查集Disjoint-set
下一篇