作者：whisper

链接：http://proprogrammar.com:443/article/383

声明：请尊重原作者的劳动，如需转载请注明出处

    写在前面

    本人抱着学习的目的写这篇文章，本人算法水平有限，在接触了相关概念，并动手操作过，看了相关的资料以后，对所学习内容做一个记录，其实主要就是拼凑看过的文章中的内容，起一个备忘的作用，如有错误，不全，幼稚的地方，还请见谅。

    用途

    并查集是一种数据结构, 常用于描述集合,经常用于解决此类问题:某个元素是否属于某个集合,或者某个元素和另一个元素是否同属于一个集合

    解释

    即有一些元素，把这些元素分组，组内元素是相互关联的，形成一棵树形结构，不同的组在一起形成森林

    有两个概念：

    weight：即一个分组中元素的数量

    height：即一个分组形成的树的高度

    有两个操作：

    find：找一个元素所在分组的根元素

    注：find操作中还可以进行路径压缩

    union：合并两个元素所在的分组为一个分组

    附加操作：

    计算分组的数量

    判断两个元素是否位于同一分组

    具体代码

    下面看一下具体的算法，重点代码有相应注释

public class UnionFind
{
	private int[] parent;
    private int size;
 
    // 设定并查集大小并初始化
    public UnionFind(int size) {
        this.size = size;
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            // 每个元素都指向自己，即自己和自己一组
            parent[i] = i;
        }
    }
     
    // 查找分组的根结点
    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }
 
    // 判断是否属于同一分组，如果根相同即属于同一分组
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    // 合并两个元素的分组
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
        if (firstRoot == secondRoot) {
            return;
        }
       
        // 分组不同，将其中一个分组的根作为另一个分组的根
        parent[firstRoot] = secondRoot;
    }
 
    /**
     * 本并查集使用数组实现，为了更直观地看清内部数据，采用打印数组
     */
    private void printArr() {
        for (int parent : this.parent) {
            System.out.print(parent + "\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
        System.out.println("初始：");
        union.printArr();
 
        System.out.println("连接了5 6");
        union.unionElements(5, 6);
        union.printArr();
 
        System.out.println("连接了1 2");
        union.unionElements(1, 2);
        union.printArr();
 
        System.out.println("连接了2 3");
        union.unionElements(2, 3);
        union.printArr();
 
        System.out.println("连接了1 4");
        union.unionElements(1, 4);
        union.printArr();
 
        System.out.println("连接了1 5");
        union.unionElements(1, 5);
        union.printArr();
 
        System.out.println("1  6 是否连接：" + union.isConnected(1, 6));
        System.out.println("1  8 是否连接：" + union.isConnected(1, 8));
    }

    上面是基本的算法，在进行两个分组合并的时候没有做特殊处理，可以进行两种处理，把weight小的分组的根节点连接到weight大的分组的根结点上，或者把height小的分组的根结点连接到height大的分组的根结点上，下面来看一下这两种情况

    使用weight的情况

public class UnionFind {
    private int[] parent;
    private int[] weight;
    private int size;
 
    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        // 在初始化分组的同时也初始化weight
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }
 
    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        // 如果已经属于同一个集合了，就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }
 
        // 将weight小的分组连接到weight大的分组上
        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
    }
 
    private void printArr(int[] arr){
        for(int p : arr){
            System.out.print(p+"\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
 
        System.out.println("初始parent：");
        union.printArr(union.parent);
        System.out.println("初始weight：");
        union.printArr(union.weight);
 
        System.out.println("连接了5 6 之后的parent：");
        union.unionElements(5, 6);
        union.printArr(union.parent);
        System.out.println("连接了5 6 之后的weight：");
        union.printArr(union.weight);
 
        System.out.println("连接了1 2 之后的parent：");
        union.unionElements(1, 2);
        union.printArr(union.parent);
        System.out.println("连接了1 2 之后的weight：");
        union.printArr(union.weight);
 
        System.out.println("连接了2 3 之后的parent：");
        union.unionElements(2, 3);
        union.printArr(union.parent);
        System.out.println("连接了2 3 之后的weight：");
        union.printArr(union.weight);
 
        System.out.println("连接了1 4 之后的parent：");
        union.unionElements(1, 4);
        union.printArr(union.parent);
        System.out.println("连接了1 4 之后的weight：");
        union.printArr(union.weight);
 
        System.out.println("连接了1 5 之后的parent：");
        union.unionElements(1, 5);
        union.printArr(union.parent);
        System.out.println("连接了1 5 之后的weight：");
        union.printArr(union.weight);
 
        System.out.println("1  6 是否连接：" + union.isConnected(1, 6));
 
        System.out.println("1  8 是否连接：" + union.isConnected(1, 8));
    }
}

    使用height的情况

public class UnionFind {
    private int[] parent;
    private int[] height;
    int size;
 
    public UnionFind(int size) {
        this.size = size;
        this.parent = new int[size];
        this.height = new int[size];
        // 在初始化分组的同时也初始化height
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            height[i] = 1;
        }
    }
 
    public int find(int element) {
        while (element != parent[element]) {
            element = parent[element];
        }
        return element;
    }
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        if (height[firstRoot] < height[secondRoot]) {
            parent[firstRoot] = secondRoot;
        } else if (height[firstRoot] > height[secondRoot]) {
            parent[secondRoot] = firstRoot;
        } else {
            /*
              如果要合并的两个集合高度一样，那么随意选一个作为根
              我这里选的是让secondRoot作为新集合的根。
              然后secondRoot高度高了一层，所以+1
            */
            parent[firstRoot] = secondRoot;
            height[secondRoot] += 1;
        }
    }
 
    private void printArr(int[] arr){
        for(int p : arr){
            System.out.print(p+"\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int n = 10;
        UnionFind union = new UnionFind(n);
 
        System.out.println("初始parent：");
        union.printArr(union.parent);
        System.out.println("初始height：");
        union.printArr(union.height);
 
        System.out.println("连接了5 6 之后的parent：");
        union.unionElements(5, 6);
        union.printArr(union.parent);
        System.out.println("连接了5 6 之后的height：");
        union.printArr(union.height);
 
        System.out.println("连接了1 2 之后的parent：");
        union.unionElements(1, 2);
        union.printArr(union.parent);
        System.out.println("连接了1 2 之后的height：");
        union.printArr(union.height);
 
        System.out.println("连接了2 3 之后的parent：");
        union.unionElements(2, 3);
        union.printArr(union.parent);
        System.out.println("连接了2 3 之后的height：");
        union.printArr(union.height);
 
        System.out.println("连接了1 4 之后的parent：");
        union.unionElements(1, 4);
        union.printArr(union.parent);
        System.out.println("连接了1 4 之后的height：");
        union.printArr(union.height);
 
        System.out.println("连接了1 5 之后的parent：");
        union.unionElements(1, 5);
        union.printArr(union.parent);
        System.out.println("连接了1 5 之后的height：");
        union.printArr(union.height);
 
        System.out.println("1  6 是否连接：" + union.isConnected(1, 6));
 
        System.out.println("1  8 是否连接：" + union.isConnected(1, 8));
    }
}

    下面略加修改代码，使之可以计算分组的数量，并对路径进行了两种优化

class UnionFind {
    private int[] parent;
    private int[] weight;
    private int size;//代表并查集中元素个数
    private int groups;//代表并查集中有多少个集合（小组）
 
    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        // 初始化分组数量
        this.groups = size;//因为初始的时候每个人自成一组，所以有多少人就有多少组
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }
 
    /* find第一种写法 */
    public int find(int element) {
        while (element != parent[element]) {
            // 路径对折，只压缩一层,改变从e 到根节点路径上每隔
            // 一个节点（除了根和其子节点）的指针，使其指向各自的祖父节点。
            parent[element] = parent[parent[element]];
            element = parent[element];
        }
        return element;
    }

    /* find第二种写法 
    public int find(int element) {
        int fa;
        while (element != parent[element]) {
            // 路径分割，只压缩一层,改变从e 到根节点路径上每个
            // 节点（除了根和其子节点）的指针，使其指向各自的祖父节点。
            fa = parent[element];
            parent[element] = parent[parent[element]];
            element = fa;
        }
        return element;
    }
    */
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        //如果已经属于同一个集合了，就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }
 
        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
 
        //合并 firstElement 和 secondElement 所在的两个组后，就少了一组。
        this.groups--;
    }
 
    // 获取分组的数量
    public int getGroups() {
        return this.groups;
    }
}

    最后再说一下路径压缩，所谓路径压缩，是因为分组形成的树，高度不一定，分组内的元素要找到根结点，可能要进行若干次判断，所以我们想让所有的非根结点都直接与根结点相连，这样最多两次判断，就可以找到根结点，下面给出最终代码

public class UnionFind
{
	private int[] parent;
    private int[] weight;
    private int size;//代表并查集中元素个数
    private int groups;//代表并查集中有多少个集合（小组）
 
    public UnionFind(int size) {
        this.parent = new int[size];
        this.weight = new int[size];
        this.size = size;
        this.groups = size;//因为初始的时候每个人自成一组，所以有多少人就有多少组
        for (int i = 0; i < size; i++) {
            this.parent[i] = i;
            this.weight[i] = 1;
        }
    }
 
    // 返回分组的根结点，一行代码
    public int find(int x) {
    	return x != parent[x] ? parent[x] = find(parent[x]) : parent[x];
    }
 
    public boolean isConnected(int firstElement, int secondElement) {
        return find(firstElement) == find(secondElement);
    }
 
    public void unionElements(int firstElement, int secondElement) {
        int firstRoot = find(firstElement);
        int secondRoot = find(secondElement);
 
        //如果已经属于同一个集合了，就不用再合并了。
        if (firstRoot == secondRoot) {
            return;
        }
 
        if (weight[firstRoot] > weight[secondRoot]) {
            parent[secondRoot] = firstRoot;
            weight[firstRoot] += weight[secondRoot];
        } else {//weight[firstRoot] <= weight[secondRoot]
            parent[firstRoot] = secondRoot;
            weight[secondRoot] += weight[firstRoot];
        }
 
        //合并 firstElement 和 secondElement 所在的两个组后，就少了一组。
        this.groups--;
    }
 
    public int getGroups() {
        return this.groups;
    }
}

    注：一行代码搞定find和union函数

     int find(int x){
    	return x != parent[x] ? parent[x] = find(parent[x]) : parent[x];
    }
    
    void union(int x, int y){
        parent[find(y)] = find(x);
    }

亲爱的读者：有时间可以点赞评论一下