开发者社区> 白头雁> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

并查集路径压缩

简介: 如何描述一个复杂的连接关系?如图,很容易判断紧邻的2个人关系,但中间的连接很多很乱,怎么判断出两个人的关系呢?并查集就是一种结构,通过保存节点以及节点上的标签,来判断这两个节点是否连接在一起。
+关注继续查看

如何描述一个复杂的连接关系?如图,很容易判断紧邻的2个人关系,但中间的连接很多很乱,怎么判断出两个人的关系呢?
并查集就是一种结构,通过保存节点以及节点上的标签,来判断这两个节点是否连接在一起。当两个节点绑定时,可以任选其中一个节点的标签,指定另一个节点。当判断两个节点是不是连接时,可以上溯节点的祖宗节点,如果祖宗节点相同,那么节点相连。此时,节点上的标签可理解为指向父亲节点。

并查集的并&查

1.节点列表

并查集中的节点只需要保存父亲节点的信息,那么线性结构字典、列表都可以。我们用一维数组,索引是自身id,值指向父亲。
初始化时每个节点指向自身

class UnionFind:
    def __init__(self,size):
        self.size = size
        self.parent = np.arange(size)
    def union(self,p,q): ##将两个节点连接在一起
    def isConnected(self,p,q): ## 判断两个节点是否相连

2.判断两个节点相连

当两个节点的祖宗节点相同时,两个节点就是连接节点。

    def find(self,p):
        assert p>=0 and p<self.size
        while (self.parent[p]!=p):
    ##向上遍历,当父节点不是自己时,
    ##那么还存在父节点,继续遍历。
            p = self.parent[p]
        return p
    def isConnected(self,p,q):
    ##当祖宗节点相同时,两个节点是连接节点
        return self.find(p)==self.find(q)

3.节点连接

当节点连接时,需要将2个节点的祖宗节点相连,可任选一个节点连接另一个节点。

def union(self,p,q):
    pRoot = self.find(p)
    qRoot = self.find(q)
    if pRoot == qRoot:
        return 
    else:
        ## 第一个节点祖宗节点指向第二节点的祖宗节点
        self.parent[pRoot] = qRoot

4.优化连接

第3小节,我们任意选择一个节点连接,这样的选择有问题。举例:一层和二层节点集合合并:

  • 如果二层节点的祖宗节点连接到一层节点上,那么就形成了一个三层节点集。
  • 另一种可能,一层节点连接到二层祖宗节点,新集还是二层。

层数越少,查询祖宗节点的代价越小,应让节点层数少的连接到层数高的。

class UnionFind:
    def __init__(self,size):
        self.size = size
        self.parent = np.arange(size)
        self.rank = np.ones(size) //记录该节点下面的层次,默认都是1层
    def unionByRank(self,p,q):
        assert p>=0 and p<self.size and q>=0 and q<self.size
        pRoot = self.find(p)
        qRoot = self.find(q)
        if pRoot == qRoot:
            return self
        else:
        ## rank小的,添加到rank大的,这样的合并不增加rank。rank节点向上遍历的步数。
            if(self.rank[pRoot] > self.rank[qRoot]):
                self.parent[qRoot] = pRoot
            elif(self.rank[qRoot] > self.rank[pRoot]):
                self.parent[pRoot] = qRoot
            else:
                self.parent[pRoot] = qRoot
                self.rank[qRoot] +=1
            return self

5.路径压缩

进一步优化,使每个节点直接指向它的祖宗节点。

    def findCompress2(self,p):
        if p!=self.parent(p):
            self.parent[p] = self.findCompress2(self.parent[p])           
        return self.parent[p]

通过递归调用,函数从某一点出发,上溯到祖宗节点,返回值传递祖宗节点。函数返回时,相当于祖宗节点向下遍历,对每一个节点父节点重新赋值。

总结:

本文两个重点:介绍了并查集和路径压缩;单向列表的反向遍历。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
进阶——细赏并查集(1)
进阶——细赏并查集(1)
17 0
Java学习路线-34:类集框架简介
Java学习路线-34:类集框架简介
27 0
Study-基于主成分分析的图像压缩和重建
Study-基于主成分分析的图像压缩和重建
80 0
Java学习路线-34:类集框架简介
Java学习路线-34:类集框架简介
55 0
摘取人工智能的明珠:达摩院语音技术发展之路
达摩院语音实验室的使命是为阿里巴巴经济体供给无处不在的语音交互智能服务,并将语音技术予以阿里云客户,进一步拓展语音技术行业边界。在阿里CIO学院攻“疫”技术公益大咖说的第十八场直播中达摩院语音实验室负责人鄢志杰将为大家讲解达摩院语音技术发展之路,一窥语音技术的大图、经济体内应用,以及通过阿里云对外进行商业输出的全貌。
1107 0
MYSQL 5.7 压缩包安装
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/catoop/article/details/51272416 版本:mysql-5.
859 0
TuShare(3):使用pandas 压缩存储hdf5文件
本文的原文连接是: http://blog.csdn.net/freewebsys/article/details/51025044 未经博主允许不得转载。 博主地址是:http://blog.csdn.net/freewebsys 1,使用压缩 hdf5在存储的是支持压缩,使用的方式是blosc,这个是速度最快的也是pandas默认支持的。 使用压缩可以提磁
2769 0
sql多文件压缩
sql语句: declare @p1 nvarchar(4000) declare @outpath nvarchar(4000) select @p1='D:\145.xls' select @outpath='D:\test123.
604 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载