圆月山庄资源网

python实现一个简单的并查集的示例代码
脚本专栏 2024/11/7 佚名
3 2
圆月山庄资源网 Design By www.vgjia.com

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。

并查集有三种基本操作，获得根节点，判断两节点是否连通，以及将两不连通的节点相连（相当于将两节点各自的集合合并）

用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实现一个简单的并查集的方式。希望对大家的学习有所帮助，也希望大家多多支持。

标签：
python,并查集,python实现并查集
圆月山庄资源网 Design By www.vgjia.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
圆月山庄资源网 Design By www.vgjia.com
www.vgjia.com 圆月山庄资源网
139,976互联网资源
144,792高清电影
21,817无损音乐
631,128技术资源

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站 透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码 爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？

根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接