最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 改进第六版的并查集

    借助递归实现查询一个节点的时候,将这个节点以及这个节点之前的所有节点全都直接指向根节点。

    // 我们的第六版Union-Find
    public class UnionFind6 implements UF {
    
        // rank[i]表示以i为根的集合所表示的树的层数
        // 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
        // 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
        private int[] rank;
        private int[] parent; // parent[i]表示第i个元素所指向的父节点
        private int size;    // 数据个数
    
        // 构造函数
        public UnionFind6(int size){
    
            rank = new int[size];
            parent = new int[size];
            this.size = size;
    
            // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
            for( int i = 0 ; i < size ; i ++ ){
                parent[i] = i;
                rank[i] = 1;
            }
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        // 查找过程, 查找元素p所对应的集合编号
        // O(h)复杂度, h为树的高度
        private int find(int p){
            if(p < 0 && p >= size)
                throw new IllegalArgumentException("p is out of bound.");
    
            // path compression 2, 递归算法
            if(p != parent[p])
                parent[p] = find(parent[p]);
            return parent[p];
        }
    
        // 查看元素p和元素q是否所属一个集合
        // O(h)复杂度, h为树的高度
        @Override
        public boolean isConnected( int p , int q ){
            return find(p) == find(q);
        }
    
        // 合并元素p和元素q所属的集合
        // O(h)复杂度, h为树的高度
        @Override
        public void unionElements(int p, int q){
    
            int pRoot = find(p);
            int qRoot = find(q);
    
            if( pRoot == qRoot )
                return;
    
            // 根据两个元素所在树的元素个数不同判断合并方向
            // 将元素个数少的集合合并到元素个数多的集合上
            if( rank[pRoot] < rank[qRoot] )
                parent[pRoot] = qRoot;
            else if( rank[qRoot] < rank[pRoot])
                parent[qRoot] = pRoot;
            else{ // rank[pRoot] == rank[qRoot]
                parent[pRoot] = qRoot;
                rank[qRoot] += 1;   // 此时, 我维护rank的值
            }
        }
    }
    

    接下来测试一下

    我们使用递归的方式写的压缩比非递归的方式整体性能上还是差一点点,这是因为在递归的过程中是有相应的开销的。

    不仅如此,其实对于我们之前的第五版的路径压缩来说,也并不是不能做到让所有的节点都直接指向根节点,只不过是不能一次性做到而已。

    并查集的时间复杂度分析

    无论是查询操作还是合并操作都是O(h)级别,这个h是树的高度,不过这个时间复杂度并不能反映h和n之间的关系。

    而对于并查集来说,它不是一个严格的二叉树或者几叉树,所以其实也没有h严格意义上它是某个log(n)级别。整体复杂度分析比较复杂。

    加入了路径压缩后,时间复杂度是O(logn)

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(10.7)更多和并查集相关的话题

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    极客文库
    程序员的加油站

    Leave a Reply

    Hi, 如果你对这款模板有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款模板有疑问,可以跟我联系哦!

    联系发布者
    • 99会员总数(位)
    • 3629资源总数(个)
    • 44本周发布(个)
    • 0 今日发布(个)
    • 105稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多