Union Find 并查集

并查集：Union Find，也叫作不相交集合（Disjoint Set），具有两个核心功能

• 查找（Find）：查找元素所在的集合（这里的集合不特指Set这种数据结构，而是广义的数据集合）
• 合并（Union）：将两个元素所在的集合合并为一个集合

主要的应用：

求连接和求路径两个问题的侧重点不一样，求连接只需要合理设计数据结构，就不需要求出路径才知道是否联通

• 连接问题：网络中节点间的连接状态
• 数学中的集合类实现

并查集 Union Find：对于一组数据，主要支持两个动作

• union(p , q)：连通两个节点
• same(p , q)：判断两个节点是否连通

Quick Find

时间复杂度：

• 查找（Find）：O（1）
• 合并（Union）：O（n）

Quick Union

时间复杂度：

• 查找（Find）：O(logn)，可以优化到 O(a(n))，a(n)<5
• 合并（Union）：O(logn)，可以优化到 O(a(n))，a(n)<5

实现

1、如何存储数据：假设并查集处理的数据都是整形，那么可以用整形数组来存储数据
2、基本实现：

public interface UnionFind {
    /**
     * 找到根节点
     *
     * @param v
     * @return
     */
    int find(int v);
    /**
     * 连通v1和v2
     *
     * @param v1
     * @param v2
     */
    void union(int v1, int v2);
    /**
     * v1与v2是否属于同一集合
     *
     * @param v1
     * @param v2
     * @return
     */
    boolean same(int v1, int v2);
}
public abstract class AbstractUnionFind implements UnionFind {
    protected int[] parents;
    public AbstractUnionFind(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity must be >=1");
        }
        parents = new int[capacity];
        // 初始化
        for (int i = 0; i < capacity; i++) {
            parents[i] = i;
        }
    }
    @Override
    public boolean same(int v1, int v2) {
        return find(v1) == find(v2);
    }
    public void rangeCheck(int v) {
        if (v < 0 || v >= parents.length) {
            throw new IllegalArgumentException("v is out of bounds");
        }
    }
}

3、QuickFind实现：在 union 两个元素时，将左边子树的所有元素均指向右边节点的根节点

public class QuickFind extends AbstractUnionFind {
    public QuickFind(int capacity) {
        super(capacity);
    }
    /**
     * 查找v所属的集合
     *
     * @param v
     * @return
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        return parents[v];
    }
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }
        // 合并两个节点时，将 v1 节点的所有元素均指向 v2 的根节点
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == p1) {
                parents[i] = p2;
            }
        }
    }
}

4、QuickUnion实现：在 union 时，使左边子树的根节点指向右边子树的根节点

public class QuickUnion extends AbstractUnionFind {
    public QuickUnion(int capacity) {
        super(capacity);
    }
    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            v = parents[v];
        }
        return v;
    }
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 != p2) {
            parents[p1] = p2;
        }
    }
}

5、左右子树元素个数平衡优化，基于QuickUnion，在数组中新增子树节点个数数组，在 union 时将元素个数少的子树的根节点指向元素个数更多子树的根节点

public class QuickUnionWithSize extends QuickUnion {
    private int[] sizes;
    public QuickUnionWithSize(int capacity) {
        super(capacity);
        // 创建size数组
        sizes = new int[capacity];
        // 初始化
        Arrays.fill(sizes, 1);
    }
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }
        if (sizes[p1] < sizes[p2]) {
            parents[p1] = p2;
            sizes[p2] += sizes[p1];
        } else {
            parents[p2] = p1;
            sizes[p1] += p2;
        }
    }
}

6、基于左右子树高度的优化，基于QuickUnion：在Union时，将高度低的子树的根节点指向高度更高的子树的根节点，高度不变；在高度一致时，被指向的根节点的高度 + 1

public class QuickUnionWithRank extends QuickUnion {
    private int[] ranks;
    public QuickUnionWithRank(int capacity) {
        super(capacity);
        ranks = new int[capacity];
        Arrays.fill(ranks, 1);
    }
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }
        if (ranks[p1] > ranks[p2]) {
            parents[p2] = p1;
        } else if (ranks[p1] < ranks[p2]) {
            parents[p1] = p2;
        } else {
            parents[p1] = p2;
            ranks[p2]++;
        }
    }
}

7、接下来是基于 QuickUnionWithRank 的优化，在这个基础上，可以在查找时对元素进行调整，达到优化的效果，具体有：

• 路径压缩（Path Compression）
• 两种更加优秀的做法：
  • 路径分裂（Path Spliting）
  • 路径减半（Path Halving）

路径压缩（Path Compression）：使路径上所有的根节点都指向根节点

public class QuickUnionWithPathCompact extends QuickUnionWithRank {
    public QuickUnionWithPathCompact(int capacity) {
        super(capacity);
    }
    @Override
    public int find(int v) {
        rangeCheck(v);
        // 将查找路径上的元素都指向根节点
        if (parents[v] != v) {
            parents[v] = find(parents[v]);
        }
        return parents[v];
    }
}

路径分裂（Path Spliting）：将 find 时路径上的节点均指向其祖父节点，从而将路径分成两条

public class QuickUnionWithPathSplit extends QuickUnionWithRank {
    @Override
    public int find(int v) {
        rangeCheck(v);
        // 路径减半，是查找路径上的每个节点指向其祖父节点
        while (parents[v] != v) {
            int tmp = parents[v];
            parents[v] = parents[parents[v]];
            v = tmp;
        }
        return v;
    }
    public QuickUnionWithPathSplit(int capacity) {
        super(capacity);
    }
}

路径减半（Path Halving）：将 find 时路径上的奇数节点指向其祖父节点

public class QuickUnionWithPathHalf extends QuickUnionWithRank{
    public QuickUnionWithPathHalf(int capacity) {
        super(capacity);
    }
    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            parents[v] = parents[parents[v]];
            v = parents[v];
        }
        return v;
    }
}

通用的并查集

基于QuickUnion 而且进行了高度优化和路径减半优化：

public class GenericQuickUnion<V> {
    private Map<V, Node<V>> nodes = new HashMap<>();
    public void makeSet(V v) {
        if (nodes.containsKey(v)) {
            return;
        }
        nodes.put(v, new Node<>(v));
    }
    /**
     * 找到v的根节点
     *
     * @param v
     * @return
     */
    private Node<V> findNode(V v) {
        Node<V> node = nodes.get(v);
        if (node == null) {
            return null;
        }
        // 判断两个对象是否相等
        while (!Objects.equals(node.value, node.parent.value)) {
            // 进行路径缩短
            node.parent = node.parent.parent;
            node = node.parent;
        }
        return node;
    }
    /**
     * 查找两个元素
     *
     * @param v
     * @return
     */
    public V find(V v) {
        Node<V> node = findNode(v);
        return node == null ? null : node.value;
    }
    public void union(V v1, V v2) {
        Node<V> node1 = findNode(v1);
        Node<V> node2 = findNode(v2);
        if ((node1 == null) || (node2 == null)) {
            return;
        }
        if (Objects.equals(node1, node2)) {
            return;
        }
        if (node1.rank < node2.rank) {
            node1.parent = node2;
        } else if (node1.rank > node2.rank) {
            node2.parent = node1;
        } else {
            node1.parent = node2;
            node2.rank++;
        }
    }
    public boolean same(V v1, V v2) {
        // 比较两个对象是否相等 (v1==v2)||(v1!=null&&v1.equals(v2))
        return Objects.equals(find(v1), find(v2));
    }
    private static class Node<V> {
        V value;
        Node<V> parent;
        int rank;
        public Node(V value) {
            this.value = value;
            parent = this;
            rank = 1;
        }
    }
}