python实现一个简单的并查集的示例代码

作者:黄天浩 时间:2023-05-15 17:14:54 

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

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

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

来源:https://segmentfault.com/a/1190000013805875

标签:python,并查集
0
投稿

猜你喜欢

  • Oracle下时间转换在几种语言中的实现

    2009-02-28 11:09:00
  • python列表与列表算法详解(2)

    2023-06-10 21:11:10
  • Python中统计函数运行耗时的方法

    2023-03-11 02:17:25
  • python实现连续变量最优分箱详解--CART算法

    2023-01-15 16:33:05
  • php面向对象程序设计介绍

    2023-05-25 05:31:11
  • 浅谈keras中的后端backend及其相关函数(K.prod,K.cast)

    2021-07-04 08:53:54
  • python tornado微信开发入门代码

    2023-11-01 01:04:59
  • 利用Python脚本实现ping百度和google的方法

    2022-03-21 06:45:37
  • OpenCV图像颜色反转算法详解

    2022-04-25 16:19:31
  • asp使用模板生成静态页面方法详解

    2007-09-24 12:29:00
  • 使用Python实现 学生学籍管理系统

    2023-08-21 18:42:47
  • 内容适应形式

    2010-03-18 16:09:00
  • Bootstrap风格的WPF样式

    2024-05-02 17:32:17
  • python捕获警告的三种方法

    2021-10-17 09:45:25
  • Win10下为VSCode配置LaTex编辑器的方法

    2023-08-27 17:20:07
  • python在Windows8下获取本机ip地址的方法

    2023-07-31 17:10:44
  • 自然语言处理之文本热词提取(含有《源码》和《数据》)

    2021-11-26 11:14:58
  • Python中POST调用Restful接口示例

    2021-03-14 19:42:19
  • vue+Element-ui实现分页效果

    2024-04-26 17:38:17
  • Anaconda环境克隆、迁移的详细步骤

    2022-02-22 08:36:47
  • asp之家 网络编程 m.aspxhome.com