欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Python实现并查集

程序员文章站 2022-03-10 22:44:20
  并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。并查集用集合中的某个元素来代表一个集合,该元素称为集合的代表元;一个集合内的所有元素组织成以代表元为根的树形结构。这样,判断两个元素是否属于同一集合,只需判断两个元素的代表元是否相同,合并两个不交集也只需对代表元做更改代表元的操作。  一般来说,一个并查集对应三个操作:初始化+查找根结点函数find+合并集合函数union。初始化字典preprepre:对于每一个元素 xxx,pre[x]pre[x]p...

  并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。并查集用集合中的某个元素来代表一个集合,该元素称为集合的代表元;一个集合内的所有元素组织成以代表元为根的树形结构。这样,判断两个元素是否属于同一集合,只需判断两个元素的代表元是否相同,合并两个不交集也只需对代表元做更改代表元的操作。

初始化

  • 字典parentparent:对于每一个元素 xxparent[x]parent[x]xx在树形结构上的父节点,如果xx是根节点,则令parent[x]=xparent[x] = x
  • 字典rankrankrank[x]rank[x]为元素xx在当前树结构中的高度(由下至上);
  • 整数sets_countsets\_count:并查集中集合的个数。

查找函数find

  • 对于查找操作,假设需要确定xx所在的的集合,也就是确定集合的代表元,可以沿着parent[x]parent[x]不断在树形结构中向上移动,直到到达根节点。
  • 路径压缩:为了加快查找速度,在查找根结点的过程中,顺便把子结点的父结点改成根结点。

合并集合函数union
Python实现并查集

  • 合并两个集合后,并查集中集合个数sets_countsets\_count减1。
class UnionFindSet(object):
    def __init__(self, data_list):
        self.parent = {}			   
        self.rank = {}				   
        self.sets_count=len(data_list) # 判断并查集里共有几个集合, 初始化默认互相独立

        for d in data_list:
            self.parent[d] = d		   # 初始化节点的父节点为自身
            self.rank[d] = 1		   # 初始化rank为1

    def find(self, d):
        """使用递归的方式来查找根节点
        路径压缩:在查找父节点的时候,顺便把当前节点移动到父节点下面
        """
        father = self.parent[d]
        if(d != father):
            father = self.find(father)
        self.parent[d] = father
        return father

    def is_same_set(self, a,b):
        """查看两个节点是不是在一个集合里面"""
        return self.find(a) == self.find(b)

    def union(self, a, b):
        """将两个集合合并在一起"""
        if not a or not b:return

        a_head = self.find(a)
        b_head = self.find(b)

        if(a_head != b_head):
            a_rank = self.rank[a_head]
            b_rank = self.rank[b_head]
            if a_rank >= b_rank:
                self.parent[b_head] = a_head
                if a_rank==b_rank:
                	self.rank[a_rank]+=1
            else:
                self.parent[a_head] = b_head
                
        self.sets_count-=1
        

if __name__ == '__main__':
    a = [1,2,3,4,5]
    ufs = UnionFindSet(a)
    ufs.union(1,2)
    ufs.union(3,5)
    ufs.union(3,1)
    print(ufs.sets_count)
    print(ufs.is_same_set(2,5))  # True
    print(ufs.parent)
    print(ufs.rank)

输出:

2
True
{1: 1, 2: 1, 3: 1, 4: 4, 5: 1}
{1: 3, 2: 1, 3: 1, 4: 1, 5: 1}

并查集用途:

  • 维护无向图的连通性。支持判断两个点是否在同一连通块内,和判断增加一条边是否会产生环。
  • 用在求解最小生成树的Kruskal算法里。

数据结构4——并查集(入门)
并查集(进阶)

本文地址:https://blog.csdn.net/Hanx09/article/details/107235923