博客

并查集(不相交集合)：用于判断一对元素是否相连，关系是动态添加，叫做动态连通性问题:

主要支持”

合并

“与”查询是否在同一个集合”操作;

底层结构是数组或者哈希表,用于表示结点指向的父节点,初始化时指向自己;

合并 就是把一个集合的根节点指向另一个集合的根节点,只要根节点一样,就表示在同一个集合里。

这种不想交集合的方法称为代表元法,以每一个结点的根节点作为一个集合的代表元。

并查集的应用:

最小生成树:Kruskal算法;

并查集的优化:

1.路径压缩(在查询过程中,更改结点指向,使得树的高度更低);

a. 隔代压缩(比较方便)

b.完全压缩(需要使用递归)

2. 按秩合并

指在合并过程中,使得高度更低的树的根节点指向高度更高的根节点,来避免合并以后树高度增加。

并查集模板

class UnionFind{
    int[] parents;
    int size;

    public UnionFind(int num){
        this.size = num;
        parents = new int[num];
        for(int i = 0;i < parents.length;i++){
            parents[i] = i;
        }
    }

    public int find(int index){
        while(index != parents[index]){
            parents[index] = parents[parents[index]];
            index = parents[index];
        }
        return index;
    }

    public void union(int index1,int index2){
        int root1 = find(index1);
        int root2 = find(index2);
        if(root1 != root2){
            parents[root2] = root1;
            this.size--;
        }
    }
}

一道并查集为哈希表来指示父子关联的题的解法，

题目见:

https://leetcode-cn.com/problems/baby-names-lcci/submissions/

class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        UnionFind unionFind = new UnionFind();
        for(String str:names){
            int index1 = str.indexOf('(');
            int index2 = str.indexOf(')');

            String name = str.substring(0,index1);
            int freuency = Integer.valueOf(str.substring(index1+1,index2));
            unionFind.size.put(name,freuency);
            unionFind.parent.put(name,name);
        }
        for(String str:synonyms){
            int index1 = str.indexOf(',');
            String name1 = str.substring(1,index1);
            String name2 = str.substring(index1+1,str.length()-1);
            unionFind.union(name1,name2);
        }


        List<String> list = new ArrayList<>();
        for(String s:unionFind.parent.keySet()){
            if(unionFind.parent.get(s).equals(s)){
                list.add(s);
            }
        }
        String[] res = new String[list.size()];
        for(int i = 0;i < list.size();i++){
            String temp = list.get(i)+'('+unionFind.size.get(list.get(i))+')';
            res[i] = temp;
        }
        return res;
    }

    class UnionFind{
        //当前节点的父节点
        Map<String,String> parent;
        //当前节点的人数
        Map<String,Integer> size;

        public UnionFind(){
            this.parent = new HashMap<>();
            this.size = new HashMap<>();
        }

        //找到x根节点
        public String find(String x){
            while(!parent.get(x).equals(x)){
                parent.put(x,parent.get(parent.get(x)));
                x = parent.get(x);
            }
            return x;
        }

        public void union(String x,String y){
             if(!parent.containsKey(x)){
                parent.put(x,x);
                size.put(x,0);
            }

            if(!parent.containsKey(y)){
                parent.put(y,y);
                size.put(y,0);
            }

            String str1 = find(x);
            String str2 = find(y);

            if(!str1.equals(str2)) {
                if(str1.compareTo(str2) > 0){
                    parent.put(str1,str2);
                    //人数累加到根节点
                    size.put(str2,size.get(str1)+size.get(str2));
                }else{
                    parent.put(str2,str1);
                    size.put(str1,size.get(str1)+size.get(str2));
                }
            }
        }
    }
}