并查集

分析

并查集，一种特殊的数据结构（它的逻辑结构本质也是一颗“树”，有唯一的根节点，任意数的子节点），它的特殊在于它只定义了两种数据操作（查找和合并）。这是用来解决连通性问题，查找（find）：就是查找任意两个节点是否连通，就是是否有共同的祖先（节点找它的父节点的过程，一层一层地找）。合并（union）：把两个不同集合的节点合并在一起。
刚开始看到并查集这个词的时候，以为它是一个算法。其实也可以说是一个算法（对树问题的一种特殊操作方式），只不过这个算法的代码实现通常要定义两个函数：find（）和union（）

我定义了一个parent[n]数组，数组下标是每个节点的编号，存储的值是每个节点的父节点


这些联通的点又称为一个分组,find函数就是寻找节点,如果下标和值相同说明该节点是祖节点.

代码

public class UF {
    private int[] items;
    private int count;

    public UF(int n){
        this.count=n;
        items=new int[n];
        //规定初始化的时候索引下标即每个位置的值
        //这个值代表所在分组
        //也就是说初始化的时候n就代表分组个数
        for (int i = 0; i < n; i++) {
            items[i]=i;
        }
    }
    public int getCount(){
        return count;
    }

    //元素所在分组根标识
    public int getRootGroup(int p){
        while (p != items[p]) {
            p = items[p];
        }
        return p;
    }
    
    //判断两个点是否在同一分组中
    public boolean connected(int p,int q){
        return getRootGroup(p)==getRootGroup(q);
    }


    public void unioned(int p,int q){
        int pgroup = getRootGroup(p);
        int qgroup= getRootGroup(q);
        if (pgroup==qgroup){
            return;
        }
        items[pgroup]=qgroup;
        count--;
    }
}
class Test{
    public static void main(String[] args) {
        UF uf = new UF(5);
        System.out.println("分组前:"+uf.getCount());
        uf.unioned(1,2);
        System.out.println("分组后:"+uf.getCount());
    }
}

在前面的代码中,还存在一些问题,我们在一条可达链路的存储上使用树结构,这样遍历该链的时候就比直接遍历要好,如果要将两棵树合并,也比直接将两条链合并的高度要低.但是我们还可以优化,从前面的代码中可以看出,我们在合并的时候,其实并没有考虑到树的高度,就会很有造成树的高度是两棵树相加的结果,但是由于树的节点是分叉的,所以我们完全可以将矮的树合并到高的树当中,这样子最后树的高度就是最高的那颗树的了,而不是两棵树相加.
其实实现很简单,只需要在进行初始化数组的时候,将每个节点的高度保存一份就可以了:

    public void unioned(int p,int q){
        int pgroup = getRootGroup(p);
        int qgroup= getRootGroup(q);
        if (pgroup==qgroup){
            return;
        }
        //如果p的高度比q的高度低
        //那么就要高的作为根节点
        if (highs[pgroup]<highs[qgroup]){
            items[pgroup]=qgroup;
        }else
            items[qgroup]=pgroup;

        count--;
    }

畅通工程

请看上图,加入有20个城市,有七条已经修建好的路,下面的七组数据代表修建好的两个城市,问最后还得修建多少条道路才将所有城市联通?
这道问题就可以利用并查集巧妙解决,我们知道,如果并查集最后count的值为1,那么就代表该数组里只有一个分组,也就是所有节点都是联通的.
所以我们只需要将那七组数据调用unioned方法,合并成一组,之后将剩余的count-1就是要修建的路了.

        UF uf = new UF(20);
        System.out.println("分组前:"+uf.getCount());
        uf.unioned(0,1);
        uf.unioned(6,9);
        uf.unioned(3,8);
        uf.unioned(5,11);
        uf.unioned(2,12);
        uf.unioned(6,10);
        uf.unioned(4,8);
        int count=uf.getCount()-1;
        System.out.println("需要修建的路剩余:"+count); //12