带权并查集python
时间: 2023-08-15 15:14:47 浏览: 79
带权并查集(Weighted Union-Find)是一种常用的数据结构,用于解决动态连通性问题。它支持两个主要操作:合并(Union)和查找(Find)。
以下是一个使用Python实现的带权并查集示例代码:
```python
class WeightedUnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.weight = [0] * n
def find(self, x):
if self.parent[x] != x:
self.compress_path(x)
return self.parent[x]
def union(self, x, y, w):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
if self.size[root_x] < self.size[root_y]:
self.parent[root_x] = root_y
self.weight[root_x] = w - self.weight[x] + self.weight[y]
self.size[root_y] += self.size[root_x]
else:
self.parent[root_y] = root_x
self.weight[root_y] = -w + self.weight[x] - self.weight[y]
self.size[root_x] += self.size[root_y]
def compress_path(self, x):
if self.parent[x] != x:
self.compress_path(self.parent[x])
self.weight[x] += self.weight[self.parent[x]]
self.parent[x] = self.parent[self.parent[x]]
def get_weight(self, x):
root = self.find(x)
return self.weight[x] - self.weight[root]
```
这个实现中,`parent`列表存储每个元素的父节点索引,`size`列表存储每个元素所在集合的大小,`weight`列表存储每个元素与其父节点的权值差。
`find()`方法用于查找元素所属的集合,并进行路径压缩优化。`union()`方法用于合并两个集合,并更新权值差。`compress_path()`方法用于路径压缩,加速后续的查找操作。`get_weight()`方法用于获取元素与其根节点的权值差。
带权并查集可以在解决一些算法问题中起到很好的作用,例如最小生成树算法中的Kruskal算法。希望这个示例代码能对你有所帮助!