快速理解Union Find算法--java代码实现

seanlook 发布于2019-08-16 10:56 / 1198人阅读

摘要：在这个方法里，查找连通分量的标识只需要的时间复杂度，但是将两个分量连接起来却需要遍历整个数组，因此时间复杂度为。

什么是Union Find

Union Find是并查集的一种数据结构。先理解两个对象之间“相连的关系”
对象p和对象q相连是指：

自反性：p和p相连
对称性：如果p和q相连，那么q和p也相连
传递性：如果p和q相连而且q和r相连，那么p和r相连

在并查集中，如果想要将连个对象相连，当且仅当这两个对象不在同一个连通分量中时，才会相连。这句话什么意思呢？也就是说，如果已经存在一条路径，使得p和q之间相通，那么就不会对后续的连接p和q的请求作出任何操作。

Union Find API

并查集需要的对外接口如下。在这里我们默认初始化时知道并查集中对象的个数并且不允许后续添加新的对象进来

UnionFind(int N) : 初始化并查集，并查集中包含N个互不相连的对象
void union(int p, int q) : 连接p,q
int find(int p) : p所在的连通分量的标识符
boolean connect(int p, int q) : 如果p和q存在于同一个分量中则返回true
int count() : 连通分量的数量

UnionFind基本设计

在这里，我们使用长度为N的整数数组来表示一个并查集的数据结构，其中下标为i的元素的值是指i对象对应的连通分量的标识。

    public class UnionFind{
        int[] id;
        int count;
        
        public UnionFind(int N){
        
        }
        public int count(){
            return count;
        }
        
        public boolean connected(int p, int q){
            return find(p) == find(q);
        }
        
        public int find(int p){
            //后面实现
        }
        
        public int union(int p, int q){
            //后面实现
        }
    }

方法一：quick find

如何证明两个对象是连通的呢？只要id[p]和id[q]对应的连通分量标识是相同的，那么p和q一定是连通的。
那么如果想要连通p和q的话，只需要将q的所有标识更新为p的标识就行了。

    public int find(int p){
        return id[p];
    }
    
    public void union(int p, int q){
        int pId = find(p);
        int qId = find(q);
        if(pId == qId) return;
        for(int i = 0 ; i
在这个方法里，查找连通分量的标识只需要O(1)的时间复杂度，但是将两个分量连接起来却需要遍历整个数组，因此时间复杂度为O(n)。如果数组很大的话，连接操作将需要大量的时间。
方法二：quick union
为了改进方法一对大容量触点过慢的情况，改进了连接操作。在这个方法里，所有的连通分量的视图是一棵树，如果将两个分量相连，那么可以将其中一个连通分量的根直接连接到另一个连通分量的根节点上。
    public int find(int p){
        while(p != id[p]) p = id[p];
        return p;
    }
    
    public void union(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) return;
        id[p] = qRoot;
        count--;
    }
方法三：weighted quick union
在上一种方法中，如果从逻辑视角，也就是树的视角查看这个连通分量的话，我们可以预想到一些极端情况，比如这棵树最终成了一个链表的形状。那么每一次查找树的根节点都意味着需要遍历这棵树的所有节点，时间复杂度显著提升。那么如何才能避免这种极端情况的出现呢？我们可以根据需要连通的两个对象的树的元素个数来决定将哪个树的根作为新的树的根。这里我们使用一个新的数据结构int[] size存储各个根节点对应的分量的大小。初始化时所有的分量的大小都为1。
    public int find(int p){
        while(p != id[p]) p = id[p];
        return p;
    }
    
    public void union(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot) return;
        if(size(pRoot) > size(qRoot)) {id[qRoot] = pRoot; size[pRoot] += size[qRoot];}
        else {id[pRoot] = qRoot; size[qRoot] += size[pRoot];}
        count--;
    }
这样就可以避免极端树的存在
Refrences
算法-图灵出版社

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云海外云主机 union-find 图像识别算法实现代码 java实现离群算法 java遗传算法实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70745.html

Union-Find并查集算法学习笔记

摘要：算法链接学习工具，，环境搭建在小伙伴的推荐下，这个学期开始上普林斯顿的算法课。一系列的整数对代表与相互连接，比如等，每一个整数代表了一个。我觉得这个可能也是并查集相关应用。这学期继续学习深入理解了就能明白了。《算法》链接：1.5 Case Study: Union-Find学习工具：mac，java8，eclipse,coursera 环境搭建在小伙伴的推荐下，这个学期开始上普林斯顿...

hzc 2019-08-14 17:08 评论0 收藏0
《算法》第一章学习笔记js实现

摘要：算法第一章学习笔记实现更多内容目标总结本书主要内容，相应算法使用来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限确定有效的并适合用计算机程序来实现的解决问题的方法。《算法》第一章学习笔记js实现更多内容目标：总结本书主要内容，相应算法使用js来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。我们关注的大多...

baishancloud 2019-08-30 13:45 评论0 收藏0
《算法》第一章学习笔记js实现

摘要：算法第一章学习笔记实现更多内容目标总结本书主要内容，相应算法使用来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限确定有效的并适合用计算机程序来实现的解决问题的方法。《算法》第一章学习笔记js实现更多内容目标：总结本书主要内容，相应算法使用js来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。我们关注的大多...

K_B_Z 2019-08-21 17:05 评论0 收藏0
《算法》第一章学习笔记js实现

摘要：算法第一章学习笔记实现更多内容目标总结本书主要内容，相应算法使用来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限确定有效的并适合用计算机程序来实现的解决问题的方法。《算法》第一章学习笔记js实现更多内容目标：总结本书主要内容，相应算法使用js来模仿实现在计算机科学领域，我们用算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法。我们关注的大多...

qingshanli1988 2019-08-01 17:47 评论0 收藏0
用并查集(find-union)实现迷宫算法以及最短路径求解

摘要：本人邮箱欢迎转载转载请注明网址代码已经全部托管有需要的同学自行下载引言迷宫对于大家都不会陌生那么迷宫是怎么生成已经迷宫要如何找到正确的路径呢用代码又怎么实现带着这些问题我们继续往下看并查集朋友圈有一种算法就做并查集什么意思呢比如现在有零本人邮箱: 欢迎转载,转载请注明网址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...

xiangchaobin 2019-08-16 10:30 评论0 收藏0