并查集

介绍

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。
哈希表查询很快，但在合并上效率不高。链表合并很快，但查询效率不高。
并查集在合并和查询上都接近 O(1)

两个主要操作：
合并（union）：将两个集合合并为一个集合。
查询（find）：确定元素属于哪个集合。 并查集中不断往上寻找他的代表元素，用于确定两个元素是否属于同一集合。

原理

并查集是将集合以树形结构进行组合的数据结构，每个元素（节点）都保存着到它代表元素（父节点）的引用。
合并：将两个集合合并，即将一颗树的根连接到另一棵树的根。
查找：根据代表元素找到最顶层的代表元素，相同则在同一集合，否则不在。

这是并查集最基本的表示方式，但它并不是很高效。
因为合并操作过多时，树的深度会加大，可能会导致创建的树严重不平衡。（查询效率会降低）

优化一：按秩合并

按秩（树的深度）合并，即总是将元素少的树连接至元素多的树上。
因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩，除非它们的秩相同。

优化二：路径压缩

路径压缩，即在查找代表元素时，将树扁平化（降低深度）。具体操作是将路径上每个元素的代表元素置为最顶层的代表元素（根）。
这样树的深度会降低，根节点下只有一层叶子节点。

关于并查集的复杂度（略）

能力不够，证明不出来。
只找到了一篇文章：
借这个问题科普一下并查集各种情况下的时间复杂度
并查集
并查集复杂度

总之，时间复杂度是很低的，接近O(1)。

实现（coding）

package UnionFind;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class UnionFind {
    // 对样本进行包裹（元素）
    public static class Element<V> {
        public V value;

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

    public static class UnionFindSet<V> {
        // 样本与元素的对应
        public HashMap<V, Element<V>> elementMap;
        // key 某个元素 value 元素的父
        public HashMap<Element<V>, Element<V>> fatherMap;
        // key 某个集合的代表元素 value 集合的大小
        public HashMap<Element<V>, Integer> sizeMap;

        /**
         * 初始化并查集
         *
         * @param list
         */
        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            // 初始化
            for (V value : list) {
                // 进行包裹
                Element<V> element = new Element<V>(value);
                // 样本与元素一一对应
                elementMap.put(value, element);
                // 父节点（代表元素）都是自己
                fatherMap.put(element, element);
                // 集合大小都为1（只有本身）
                sizeMap.put(element, 1);
            }
        }

        /**
         * 查找元素的代表元素
         */
        private Element<V> findHead(Element<V> element) {
            // 代表元素不是本身时，放入栈中，且一直往上找
            Stack<Element<V>> path = new Stack<>();
            while (element != fatherMap.get(element)) {
                path.push(element);
                element = fatherMap.get(element);
            }
            // 找到代表元素后，将栈中所有子节点的代表元素置为最顶层代表元素
            while (!path.isEmpty()) {
                fatherMap.put(path.pop(), element);
            }
            return element;
        }

        /**
         * 判断两样本是否在同一集合
         */
        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;
        }

        /**
         * 合并集合
         */
        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                // 获取对应元素
                Element<V> aFather = findHead(elementMap.get(a));
                Element<V> bFather = findHead(elementMap.get(b));
                // 不在同一集合时，将节点少的集合添加到节点多的集合中
                if (aFather != bFather) {
                    Element<V> big = sizeMap.get(aFather) >= sizeMap.get(bFather) ? aFather : bFather;
                    Element<V> small = big == aFather ? bFather : aFather;
                    fatherMap.put(small, big);
                    sizeMap.put(big, sizeMap.get(aFather) + sizeMap.get(bFather));
                    sizeMap.remove(small);
                }
            }
        }
    }

}

应用

岛问题
【题目】
一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如
果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？
【举例】
001010
111010
100100
000000
这个矩阵中有三个岛
【进阶】
如何设计一个并行算法解决这个问题

1. 使用递归暴力求解
2. 将矩阵进行划分，然后每块都使用递归求解，最后进行合并（这里只分成了两块，使用两个线程模拟）

实现：

package UnionFind;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CountDownLatch;

public class Application {
    /**
     * 数组封装后的对象
     */
    private static class Node {
        int i;
        int j;
        int value;

        public Node(int i, int j, int value) {
            this.i = i;
            this.j = j;
            this.value = value;
        }
    }

    private static Node[][] nodes;
    private static UnionFind.UnionFindSet<Node> unionFindSet;

    /**
     * 第二种解法
     * 也是递归感染，但是是并行的。将矩阵进行划分，然后分别统计，最后将结果合并。
     */
    public static int countIslandsUnionFind(int[][] m) throws InterruptedException {
        if (m == null || m[0] == null) {
            return 0;
        }
        // 获取矩阵大小
        int N = m.length;
        int M = m[0].length;
        // 设置返回值数组，供两个线程使用
        final int[] results = {0, 0};
        // 将数组的元素封装成对象，并将岛加入列表，放入并查集
        List<Node> list = new ArrayList<>();
        nodes = new Node[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Node node = new Node(i, j, m[i][j]);
                nodes[i][j] = node;
                if (m[i][j] == 1) {
                    list.add(node);
                }
            }
        }
        // 初始化并查集
        unionFindSet = new UnionFind.UnionFindSet<Node>(list);
        // 开启两个线程，分别统计一半
        final CountDownLatch latch = new CountDownLatch(2);
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M / 2; j++) {
                        if (nodes[i][j].value == 1) {
                            results[0]++;
                            infectUnionFind(i, j, 0, N, 0, M / 2);
                        }
                    }
                }
                latch.countDown();
            }
        });
        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < N; i++) {
                    for (int j = M / 2; j < M; j++) {
                        if (nodes[i][j].value == 1) {
                            results[1]++;
                            infectUnionFind(i, j, 0, N, M / 2, M);
                        }
                    }
                }
                latch.countDown();
            }
        });
        t1.start();
        t2.start();
        latch.await();
        // 合并，判断分界线两侧的元素是否是相连的岛
        int result = results[0] + results[1];
        for (int i = 0; i < N; i++) {
            if (nodes[i][M / 2 - 1].value == nodes[i][M / 2].value && nodes[i][M / 2 - 1].value == 2 && !unionFindSet.isSameSet(nodes[i][M / 2 - 1], nodes[i][M / 2])) {
                unionFindSet.union(nodes[i][M / 2 - 1], nodes[i][M / 2]);
                result--;
            }
        }
        return result;
    }

    /**
     * 感染过程
     */
    private static boolean infectUnionFind(int i, int j, int N1, int N2, int M1, int M2) {
        if (i < N1 || i >= N2 || j < M1 || j >= M2 || nodes[i][j].value != 1) {
            return false;
        }
        // i,j没有越界且当前位置为1
        nodes[i][j].value = 2;
        // 感染上下左右四个位置
        if (infectUnionFind(i + 1, j, N1, N2, M1, M2)) {
            unionFindSet.union(nodes[i][j], nodes[i + 1][j]);
        }
        if (infectUnionFind(i - 1, j, N1, N2, M1, M2)) {
            unionFindSet.union(nodes[i][j], nodes[i - 1][j]);
        }
        if (infectUnionFind(i, j + 1, N1, N2, M1, M2)) {
            unionFindSet.union(nodes[i][j], nodes[i][j + 1]);
        }
        if (infectUnionFind(i, j - 1, N1, N2, M1, M2)) {
            unionFindSet.union(nodes[i][j], nodes[i][j - 1]);
        }
        return true;
    }

    /**
     * 第一种解法
     * 递归感染
     * 时间复杂度 O(N*M)
     */
    public static int countIslands(int[][] m) {
        if (m == null || m[0] == null) {
            return 0;
        }
        // 获取矩阵大小
        int N = m.length;
        int M = m[0].length;
        int result = 0;
        // 遍历矩阵中每个元素
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 是岛则进行感染过程
                if (m[i][j] == 1) {
                    result++;
                    infect(m, i, j, N, M);
                }
            }
        }
        return result;
    }

    /**
     * 递归传染
     */
    private static void infect(int[][] m, int i, int j, int N, int M) {
        if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
            return;
        }
        // i,j没有越界且当前位置为1
        m[i][j] = 2;
        // 感染上下左右四个位置
        infect(m, i + 1, j, N, M);
        infect(m, i - 1, j, N, M);
        infect(m, i, j + 1, N, M);
        infect(m, i, j - 1, N, M);
    }
}

测试：

import UnionFind.Application;
import org.junit.Test;

public class UnionFindTest {
    @Test
    public void countIslandsTest() throws InterruptedException {
        int[][] m1 = new int[1000][1000];
        int[][] m2 = new int[1000][1000];
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < 1000; j++) {
                int temp = (int) (Math.random() * 2);
                m1[i][j] = temp;
                m2[i][j] = m1[i][j];
            }
        }
        System.out.println("递归感染过程（单线程）：" + Application.countIslands(m1));
        System.out.println("划分地图，多线程并行：" + Application.countIslandsUnionFind(m2));

    }
}

运行结果：

递归感染过程（单线程）：66575
划分地图，多线程并行：66575

进程已结束,退出代码0

总结

最后划分矩阵分别使用递归，最后合并的代码写了好久。
对Java常用的数据结构还不是很熟悉，又不想改动已经写好的并查集结构。所以写了Node对象，使用nodes数组对矩阵进行复制。
（毕竟要保证并查集中的元素都不一样，虽然值可能一样。而Java中，不new一个Integer对象，而是直接赋值，会自动装箱。自动装箱会将-128~127的数的对象引用指向静态代码块中创建好的对象）
另外，要注意边界的条件。
coding能力有限，只实现了划分一次。
如果是根据矩阵大小动态地划分矩阵，分给多个cpu运算，最后进行合并。会是一个理想的解决方案。
这里就不实现了，练习结束！

顺带一提，时间复杂度的证明比较复杂，所以这里只实现用法和了解大概的复杂度，不深究具体的复杂度及其证明。

---

参考文章：
并查集基础
算法：并查集
并查集(通俗易懂)
【算法与数据结构】—— 并查集
借这个问题科普一下并查集各种情况下的时间复杂度
并查集
并查集复杂度