Java 实现并查集查询、合并_java实现并查集

前言

【题目描述】
给定一个没有重复值的整型数组 arr，初始时认为 arr 中每一个数各自都是一个单独的集合。
请设计一种叫 UnionFind 的结构，并提供以下两个操作。
1）boolean isSameSet(int a, int b)：查询 a 和 b 这两个数是否属于一个集合。
2）void union(int a, int b)：把 a 所在的集合与 b 所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合。

【要求】
如果调用 isSameSet 和 union 的总次数逼近或超过 O(N)，请做到单次调用 isSameSet 或 union
方法的平均时间复杂度为 O(1)。

思路

1. 一开始每个元素自己形成单独的集合，同时其父结点指向自己【这里父结点为当前集合的根结点】；
   
2. 定义查找集合根结点的方法，依次查找father结点，查找过程中将路过的所有结点都直接挂到根结点上，压缩查询路径，降低查询时间复杂度；

3. 判断两个元素是否处于同一集合，即查询两个元素对应集合的根结点是否一致即可；
4. 合并两个集合遵守如下原则：
   a.如果两个集合根结点一致，则说明属于同一个集合，无须进行合并操作；
   b.如果两个集合根结点不一致，则需要进行合并操作，将集合个数少的集合合并到集合个数多的集合【本质目的还是降低查找集合根结点层级，如下图查找结点2，如果以集合少的4为根结点，则查找层级+1】，如下图：
   

代码实现

• 定义结点类Node；

    private static class Node<V> {
        private V value;

        public Node(V value) {
            this.value = value;
        }
    }

1
2
3
4
5
6
7
8

• 实现并查集类UnionFindSet；

 public static class UnionFindSet<V> {
        /**
         * V -> Node 关系映射
         */
        private HashMap<V, Node<V>> elementMap;
        /**
         * 存储Node以及其集合根结点
         */
        private HashMap<Node<V>, Node<V>> fatherMap;
        /**
         * 存储集合根结点元素 以及其集合元素数量
         */
        private HashMap<Node<V>, Integer> sizeMap;

        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            makeSet(list);
        }

        private void makeSet(List<V> list) {
            for (V v : list) {
                Node node = new Node(v);
                elementMap.put(v, node);
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        /**
         * 递归查找一个Node对应的头结点
         *
         * @return
         */
        private Node findHead(Node node) {
            if (node == null) {
                return null;
            }
            Node father = fatherMap.get(node);
            if (father != node) {
                father = findHead(father);
            }
            //将当前结点直接挂接到头结点上，降低层级
            fatherMap.put(node, father);
            return father;
        }

        /**
         * 查找两个结点是否处于同一集合
         *
         * @param a 结点a
         * @param b 结点b
         * @return
         */
        public boolean isSameSet(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            }
            return false;
        }

        /**
         * 合并两个集合
         *
         * @param a
         * @param b
         */
        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                Node aHead = findHead(elementMap.get(a));
                Node bHead = findHead(elementMap.get(b));
                //两者头结点相同，不需要合并
                if (aHead == bHead) {
                    return;
                }
                int aSize = sizeMap.get(aHead);
                int bSize = sizeMap.get(bHead);
                //将结点数少的挂在结点数多的上面
                if (aSize <= bSize) {
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSize + bSize);
                } else {
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSize + bSize);
                }
            }

        }

    }
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

测试用例

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        UnionFindSet set = new UnionFindSet(list);
        set.union(1, 3);
        set.union(2, 4);

        boolean sameSet1 = set.isSameSet(2, 3);
        boolean sameSet2 = set.isSameSet(2, 4);
        System.out.println(sameSet1);
        System.out.println(sameSet2);

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

输出结果

false
true
1
2

结语

如果以上文章对您有一点点帮助，希望您不要吝啬的点个赞加个关注，您每一次小小的举动都是我坚持写作的不懈动力！ღ( ´･ᴗ･` )