并查集路径压缩

如何描述一个复杂的连接关系?如图,很容易判断紧邻的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]

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

总结:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏犀利豆的技术空间

Redis 的基础数据结构(二) 整数集合、跳跃表、压缩列表

上篇文章写了 Redis 基础数据结构的可变字符串、链表、字典。大家可以点击链接查看。今天我们继续研究 Redis 的基础数据结构。

943
来自专栏Aloys的开发之路

ACM竞赛之输入输出(以C与C++为例)

本文转自互联网,内容、排版有修正。 在ACM程序设计竞赛中,一道题目的所有测试数据是放在一个文本文件中,选手将一道题目的程序提交给评判系统运行,程序从该文件中读...

3895
来自专栏闻道于事

Java异常处理中的恢复模型

2714
来自专栏数据结构与算法

P1965 转圈游戏

题目描述 n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 ...

3588
来自专栏java初学

海量数据处理

47014
来自专栏大闲人柴毛毛

Redis源码分析(三)——Redis数据结构-字典

1. 数据结构 ? 1.1 哈希表 typedef struct dictht{ dictEntry **table; unsigned long s...

3015
来自专栏精讲JAVA

8 张图理解 Java

一图胜千言,下面图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

871
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.7节C风格数据结构内存布局之结构体数组

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

721
来自专栏祥子的故事

Python编程快速上手 让繁琐工作自动化 | 第三章 :实践项目

3076
来自专栏Java后端技术栈

8 张图理解 Java

一图胜千言,下面图解均来自Program Creek 网站的Java教程,目前它们拥有最多的票选。如果图解没有阐明问题,那么你可以借助它的标题来一窥究竟。

661

扫码关注云+社区

领取腾讯云代金券