并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
并查集有三种基本操作,获得根节点,判断两节点是否连通,以及将两不连通的节点相连(相当于将两节点各自的集合合并)
用UnionFind类来表示一个并查集,在构造函数中,初始化一个数组parent,parent[i]表示的含义为,索引为i的节点,它的直接父节点为parent[i]。初始化时各个节点都不相连,因此初始化parent[i]=i,让自己成为自己的父节点,从而实现各节点不互连。
def __init__(self, n): self.parent = list(range(n))
由于parent[i]仅表示自己的直接父节点,查询两个节点是否相交需要比较它们的根节点是否相同。因此要封装一个查询自己根节点的方法。
def get_root(self, i): while i != self.parent[i]: i = self.parent[i] return i
接下来可以通过来比较根节点是否相同来判断两节点是否连通。
def is_connected(self, i, j): return self.get_root(i) == self.get_root(j)
当要连通两个节点时,我们要将其中一个节点的根节点的parent,设置为另一个节点的根节点。注意,连通两个节点并非仅仅让两节点自身相连,实际上是让它们所属的集合实现合并。
def union(self, i, j): i_root = self.get_root(i) j_root = self.get_root(j) self.parent[i_root] = j_root
接下来我们做两个小优化。
由于调用get_root时需要通过不断找自己的直接父节点,来寻找根节点,如果这棵树的层级过深,会导致性能受到严重影响。因此我们需要在union时,尽可能的减小合并后的树的高度。
在构造函数中新建一个数组rank,rank[i]表示节点i所在的集合的树的高度。
因此,当合并树时,分别获得节点i和节点j的root i_root和j_root之后,我们通过访问rank[i_root]和rank[j_root]来比较两棵树的高度,将高度较小的那棵连到高度较高的那棵上。如果高度相等,则可以随便,并将rank值加一。
def union(self, i, j): i_root = self.get_root(i) j_root = self.get_root(j) if self.rank[i_root] == self.rank[j_root]: self.parent[i_root] = j_root self.rank[j_root] += 1 elif self.rank[i_root] > self.rank[j_root]: self.parent[j_root] = i_root else: self.parent[i_root] = j_root
通过对union操作的改良可以防止树的高度过高。我们还可以对get_root操作本身进行优化。
当前每次执行get_root时,需要一层一层的找到自己的父节点,很费时。由于根节点没有父节点,并且文章开始处提到过如果一个节点没有父节点,那么它的父节点就是自己,因此可以说只有根节点的父节点是自己本身。现在我们加上一个判断,判断当前节点的父节点是否为根节点,如果不为根节点,就递归地将自己的父节点设置为根节点,最后返回自己的父节点。
def get_root(self, i): if self.parent[i] != self.parent[self.parent[i]]: self.parent[i] = self.get_root(self.parent[i]) return self.parent[i]
以上是python实现一个简单的并查集的方式。希望对大家的学习有所帮助,也希望大家多多支持。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
稳了!魔兽国服回归的3条重磅消息!官宣时间再确认!
昨天有一位朋友在大神群里分享,自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址,com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后,确实是网易的网址,也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情,因为以前都没有出现这样的情况,现在突然提示跳转到国服战网的网址,是不是说明了简体中文客户端已经开始进行更新了呢?
更新日志
- 《寂静之地》设计师:该作时间线设计会更有创作空间
- 西普大陆隐藏宠物收集攻略 怎么抓到隐藏宠物
- 西普大陆新手必看攻略 帮你前期少走弯路
- 金铲铲之战S9阵容推荐攻略 6套阵容分享
- dnf手游追忆光环外观选哪个 dnf手游追忆光环外观选择推荐
- 怎么获得dnf手游紫色曲玉 dnf手游紫色曲玉获取方法一览
- dnf手游洗点水怎么获得 dnf手游洗点水获取方法介绍
- 万代南梦宫遭中国玩家抵制 《铁拳8》被疯狂刷差评
- 曝侃爷分手登微博热搜 网友:穿衣意见不合?
- 《暗喻幻想:ReFantazio》M站2024高分榜排名第三 超越《最终幻想7:重生》
- 赛季末发育路上分英雄推荐,狄仁杰A就行
- 小乔克制攻略:除了兰陵王还有更多好选
- 王者荣耀:对抗路难度排行,花木兰最能秀
- 群星《新说唱2024 第3期 (下)》[FLAC/分轨][89.04MB]
- 群星《歌手2024 第2期》[320K/MP3][95.59MB]