并查集是一种维护集合的数据结构,用于处理一些不相交集合的合并及查询问题,主要有查找和合并两种操作。
看一个具体的问题,已知一系列关于变量的等式,比如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
并查集就是为了简化多个集合查询和合并的,并查集是通过指向来维护集合,如果最终指向相同则说明他们属于同一个集合,最后一个元素指向自身,比如
如果要合并这两个集合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}
上面代码实现了并查集功能,但是并未做优化处理,在合并两个集合时,一般需要考虑将层级较少的根元素指向层级较多的根元素。比如上面两个集合a->b和c->d->e,一般我们会让b指向e,而不是让e指向b,因为这样可以减少合并后整体的层级。