python克鲁斯卡尔算法
时间: 2023-11-25 19:51:02 浏览: 38
以下是Python实现Kruskal算法的示例代码:
```python
# 定义边的类
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
# 定义并查集类
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
# 定义Kruskal算法函数
def kruskal(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda x: x.w)
res = []
for e in edges:
if uf.union(e.u, e.v):
res.append(e)
return res
```
其中,边的类Edge包含三个属性:起点u,终点v和权重w。并查集类UnionFind包含两个方法:find(x)用于查找x所在的集合的根节点,union(x, y)用于将x和y所在的集合合并。Kruskal算法函数kruskal(n, edges)接受节点数n和边列表edges作为输入,返回最小生成树的边列表res。