Python 中的并集查找算法
本教程将讨论如何在 Python 中实现 union-find 算法。
并集算法
在编程中，选择最优的数据结构对于保证我们代码的高效性能非常重要。
union-find 数据结构用于记录和跟踪一组给定的值，这些值被划分为许多不重叠的不相交子集。这种数据结构也称为不相交子集。
它支持对子集的两种操作，Find 和 Union。让我们在下面讨论它们。
Find 操作查找给定元素的子集。它提供子集代表，通常是这个集合中的一个项目。
联合操作合并两个子集。只有当它们属于同一集合时，它才会组合子集，然后两个子集共享代表。
我们使用两个 Find 操作来比较两个元素并检查它们是否属于同一个子集。如果它们具有相同的代表，它们就有，然后我们执行 Union 操作以合并两个元素所属的两个子集。
Union-Find 算法具有不同的应用，例如查找最小生成树、检测无向图中的循环等。
在 Python 中实现 Union-Find 算法
为了在 Python 中实现 Union-Find，我们使用树的概念。树的根可以作为代表，每个节点都会持有对其父节点的引用。
Union-Find 算法将遍历父节点到达根，并通过附加它们的根来组合两棵树。
例子：
class uf_ds:
parent_node = {}
def make_set(self, u):
for i in u:
self.parent_node[i] = i
def op_find(self, k):
if self.parent_node[k] == k:
return k
return self.op_find(self.parent_node[k])
def op_union(self, a, b):
x = self.op_find(a)
y = self.op_find(b)
self.parent_node[x] = y
def display(u, data):
print([data.op_find(i) for i in u])
u = [1, 3, 5, 7]
data = uf_ds()
data.make_set(u)
display(u, data)
data.op_union(1, 5)
display(u, data)
data.op_union(7, 1)
display(u, data)
输出：
[1, 3, 5, 7]
[5, 3, 5, 7]
[5, 3, 5, 5]
在上面的示例中，我们在 Python 中实现了 Union-Find 算法。我们创建一个类来表示一个不相交的集合。
此类定义联合和查找操作方法并显示集合。在使用 Find 操作比较值之后，我们定义这个类的一个对象并使用 Union 操作组合树。
注意每次操作后的结果。
然而，在上述实现的最坏情况下，时间复杂度变为线性。树被串起来，并不比链表好。
因此，引入了两种优化技术来改进 Union-Find 算法。
第一个涉及树的排序以改进 Union 操作。树的深度会增加朴素方法的时间复杂度，因此这种技术确保我们将较小树的根附加到较大的树。
这将 Python 中 Union-Find 算法的最坏情况时间复杂度提高到几乎 O(Log(n))。
路径压缩是另一种用于提高 Python 中联合查找算法效率的技术。这种方法旨在展平给定的树并改进 Find 操作。
这旨在使发现的根节点成为节点 n 的父节点。这消除了遍历直接节点的需要。
当节点 n 是给定子树的根时，此压缩下面的所有元素。
这两种技术在提高联合查找算法的时间复杂度方面是有效的，甚至低于 (OLog(n))。它们相互补充。
我们可以在我们的代码中实现它们，如下所示。
class ufds:
parent_node = {}
rank = {}
def make_set(self, u):
for i in u:
self.parent_node[i] = i
self.rank[i] = 0
def op_find(self, k):
if self.parent_node[k] != k:
self.parent_node[k] = self.op_find(self.parent_node[k])
return self.parent_node[k]
def op_union(self, a, b):
x = self.op_find(a)
y = self.op_find(b)
if x == y:
return
if self.rank[x] > self.rank[y]:
self.parent_node[y] = x
elif self.rank[x] < self.rank[y]:
self.parent_node[x] = y
else:
self.parent_node[x] = y
self.rank[y] = self.rank[y] + 1
def display(u, data):
print([data.op_find(i) for i in u])
u = [1, 3, 5, 7]
data = ufds()
data.make_set(u)
display(u, data)
data.op_union(1, 5)
display(u, data)
data.op_union(7, 1)
display(u, data)
输出：
[1, 3, 5, 7]
[5, 3, 5, 7]
[5, 3, 5, 5]
注意 op_union() 和 op_find() 函数的变化，分别用于实现联合排序和路径压缩技术。
Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.
LinkedIn