python实现一个简单的并查集

wawor4827 发布于2019-07-31 12:23 / 3178人阅读

摘要：并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。在构造函数中新建一个数组，表示节点所在的集合的树的高度。以上是实现一个简单的并查集的方式。

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

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

用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实现一个简单的并查集的方式。

GPU云服务器云服务器并查集 python实现简单爬虫功能简单编写一个html 您编一个简单点的

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45553.html

面试常考算法题之并查集问题

摘要：很显然，我们可以使用并查集来求解。并查集是用来将一系列的元素分组到不相交的集合中，并支持合并和查询操作。理论总是过于抽象化，下面我们通过一个例子来说明并查集是如何运作的。采用这个方法，我们就可以写出最简单版本的并查集代码。朋友圈问题现在有 105个用户，编号为 1- 105。已知有 m 对关系，每一对关系给你两个数 x 和 y ，代表编号为 x 的用户和编号为 y 的用户是在一个圈子中，例如...

番茄西红柿 2021-11-26 11:11 评论0 收藏2637
[Leetcode] Graph Valid Tree 图与树

摘要：这样就将一个集合的节点归属到同一个集合号下了。最后如果并查集中只有一个集合，则说明可以构建树。 Graph Valid Tree Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check w...

luqiuwen 2019-08-14 12:36 评论0 收藏0
leetcode200. Number of Islands

摘要：题目要求提供一个二维数组表示一张地图，其中代表陆地，代表海洋。这里使用一个新的二维数组来表示对应地图上的元素属于哪个并查集。在合并的时候先进行判断，如果二者为已经相连的陆地，则无需合并，否则将新的二维数组上的元素指向所在的并查集。题目要求 Given a 2d grid map of 1s (land) and 0s (water), count the number of isla...

Zoom 2019-08-16 10:45 评论0 收藏0