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
猜你喜欢
- 在Linux中,可以使用nohup将脚本放置后台运行,如下:nohup python myscript.py params1 > no
- listlist是一种有序的集合,可以随时添加和删除其中的元素。跟java不一样的是 可以使用arr[-1] 0>-x >=-
- 本文实例讲述了Python 多线程,threading模块,创建子线程的两种方式。分享给大家供大家参考,具体如下:GIL(全局解释器锁)是C
- 功能是从客户端向服务发送一个字符串, 服务器收到后将字符串重新发送给客户端,同时,在连接建立之后,服务器可以向客户端发送任意多的字符串客户端
- 如何利用pandas读取csv数据并绘图导包,常用的numpy和pandas,绘图模块matplotlib,import matplotli
- 在日常工作中,我们常常会用到需要周期性执行的任务,一种方式是采用 Linux 系统自带的 crond 结合命令行实现,另外一种方式是直接使用
- python爬虫模块Request的安装在cmd中,使用如下指令安装requests:pip install requestspython爬
- 这里我不想采用诸如ubuntu下的apt-get install方式进行python的安装,而是在linux下采用源码包的方式进行pytho
- 1、首先停止正在运行的MySQL进程 Linux下,运行 killall -TERM mysqld Windows下,如果写成服务的 可以运
- 运算符的优先级和关联性运算符的优先级和关联性: 运算符的优先级和关联性决定了运算符的优先级。运算符优先级这用于具有多个具有不同优先级的运算符
- 使用 pyInstaller 将 python 程序生成可直接运行的程序,这个exe程序就可以在Windows 或 Ma
- 要判断自定义对象的类型,用__class__方法,或者用isinstance(object, class-or-type-or-tuple)
- pytorch里面的maxpool,有一个属性叫ceil_mode,这个属性在api里面的解释是ceil_mode: when True,
- 今天想用python做个demo,含两个子图的动态gif,代码如下:import matplotlib.pyplot as pltimpor
- 手动安装python3.6只需要将其ppa源加入apt仓库列表即可,但是最近常用的一个源 ppa:jonathonf/python
- 本文实例讲述了python 队列基本定义与使用方法。分享给大家供大家参考,具体如下:队列的特征是:先进先出应用场景:消息通信、多进程间的协同
- Python最近挺火呀,比鹿晗薛之谦还要火,当然是在程序员之间。下面我们看看有关Python的相关内容。上一篇文章我们已经介绍了部分Pyth
- 代码如下,U我认为对于新手来说最重要的是学会rnn读取数据的格式。# -*- coding: utf-8 -*-""&q
- 本来是只用Tenorflow的,但是因为TF有些Numpy特性并不支持,比如对数组使用列表进行切片,所以只能转战Pytorch了(pytor
- 文件处理流程1.打开文件,得到文件句柄并赋值给一个变量2.通过句柄对文件进行操作3.关闭文件 r模式,默认模式,文件不存在则报错w