数据结构与算法之 并查集

1. 什么是并查集？并查集解决哪类问题？

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

上图是我在网络上找的一张很有意思的图片，相信很多人都看过金庸的小说。面对这样的问题：

1. 如何将杨过和小龙女合并为一个教派，并且合并之后便于查找此二人是否是同一教派？
2. 请问虚竹和张三丰是否是一个门派的？
3. 图中共有几个门派？

面对这些问题，最适合用并查集来解决，时间和空间复杂度都比较低。读者面对这样的问题可以试着脑补其他的数据结构，也不是不能做，试着分析下其时间复杂度。

2. 并查集的基本操作

并查集初始化

把每个点所在集合初始化为其自身。

通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。

public class UnionFind {
    // 集合中的节点
    public static class Node {
        // whatever you like
    }
  // 借助的基础数据结构为HashMap
    public static class UnionFindSet {
        public HashMap<Node, Node> fatherMap;  //  k->v k和v在同一个集合
        public HashMap<Node, Integer> sizeMap;  // 集合内的节点数量
        public UnionFindSet() {
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
        }
        // 初始化所有节点
        public UnionFindSet(List<Node> nodes) {
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            makeSets(nodes);
        }
        // 初始化要给到所有样本
        public void makeSets(List<Node> nodes) {
            fatherMap.clear();
            sizeMap.clear();
            for (Node node : nodes) {
                fatherMap.put(node, node);  // 每个节点指向自己
                sizeMap.put(node, 1);   // 每个节点各自的集合只有自己
            }
        }
    }
}

并查集初始化与打扁

查找

查找元素所在的集合，即根节点。

// 该方法不但能找到元素所在集合，而且还能将原来不扁平的集合打扁
    private Node findHead(Node node) {
            Node father = fatherMap.get(node);
            if (father != node) {
                father = findHead(father);
            }
            fatherMap.put(node, father);
            return father;
        }

查找两节点是否在同一个集合里

        // 判断两个节点是否是同一个集合
        public boolean isSameSet(Node a, Node b) {
            return findHead(a) == findHead(b);
        }

合并

将两个元素所在的集合合并为一个集合。

// 并集操作
        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aHead = findHead(a);  // 这个过程会将集合a打扁
            Node bHead = findHead(b);
            if (aHead != bHead) {
                int aSetSize= sizeMap.get(aHead); // a所在集合的大小
                int bSetSize = sizeMap.get(bHead); // b所在集合的大小
                if (aSetSize <= bSetSize) {
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                } else {
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                }
            }
        }

参考链接： 百度百科：并查集

版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！