并查集

作者: null12 | 来源:发表于2018-03-21 20:36 被阅读0次

    一、定义

    并查集(Union Find)是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(动态连通性问题),常常在使用中以森林来表示。

    动态连通性
    对于一系列整数,其中每个整数都表示一种类型的对象,一对整数p和q可以被理解为“p和q是相连的”。我们假设“相连”是一种对等的关系,这意味着“相连”具有以下性质:
    ①自反性:p和p是相连的;
    ②对称性:如果p和q是相连的,那么q和p也是相连的;
    ③传递性:如果p和q是相连的,q和r是相连的,那么p和r也是相连的。

    1-1 动态连通性

    并查集API定义:

    1-2 并查集API定义
    注:union方法用于将两个分量合并;find方法返回指定触点所在的连通分量标识

    二、实现

    基于加权和路径压缩的并查集算法:
    1. 加权:
    用一个数组保存当前各个连通分量的高度(权重),初始时都为1。
    每次归并时,将权重小的连通分量接到权重大的连通分量上,同时权重加1。
    2. 路径压缩:
    每次查找一个触点的所属的连通分量标识(根结点)时,将所有路径上遇到的触点直接链接到根节点。


    2-2 算法轨迹(不含压缩路径)

    源码:

    public class WeightedQuickUnionPathCompressionUF {
        private int[] parent;   // parent[i]:结点i的父亲结点
        private int[] size;     // size[i]:结点i所在的连通分量权重
        private int count;      // 连通分量个数
     
        public WeightedQuickUnionPathCompressionUF(int n) {
            count = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;    // 初始时每个连通分量权重为1
            }
        }
     
        public int count() {
            return count;
        }
     
        /**
         * 返回结点p所在的连通分量标识
         */
        public int find(int p) {
            // 查找p的根节点root
            while (p != parent[p])
                p = parent[p];
            int root = p;
     
            // 将所有路径上遇到的触点直接链接到根节点
            while (p != root) {
                int tmp = parent[p];
                parent[p] = root;
                p = tmp;
            }
            return root;
        }
     
        /**
         * 判断结点p和结点q是否连通
         */
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
     
        /**
         * 根据权重,将结点p和结点q所在的连通分量合并
                      * (即将p的根结点和q的根结点连接) 权重相同时, 以p所在连
                      *  通分量作为连通标识
         */
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ)
                return;
     
            // 将权重小的连通分量链接到权重大的连通分量上
            if (size[rootP] < size[rootQ]) {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            } else {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }
            count--;
        }
    }
    

    三、性能分析

    并查集算法有很多种,下图给出了各类并查集算法的比较。

    3-1 各类并查集算法比较
    注:本文的实现中采用的是 基于加权和路径压缩的并查集算法 ,时间复杂度接近于O(1)。

    相关文章

      网友评论

        本文标题:并查集

        本文链接:https://www.haomeiwen.com/subject/bcenqftx.html