Python实现并查集

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

初始化

• 字典$parent$：对于每一个元素 $x$，$parent[x]$为$x$在树形结构上的父节点，如果$x$是根节点，则令$parent[x] = x$；
• 字典$rank$：$rank[x]$为元素$x$在当前树结构中的高度（由下至上）；
• 整数$sets\_count$：并查集中集合的个数。

查找函数find

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

合并集合函数union

• 合并两个集合后，并查集中集合个数$sets\_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