用python使用并查集的思想求解最小生成树问题 输入格式: n,e ;n端点数量、m边的数量 n1,n2,e1 ; n1端点1,n2端点2 e1边的权值 。。。 ;这样的信息有e行 输出格式: n1 n2 e1 生成树中的边的信息 生成树的权值之和即最小成本
时间: 2024-02-05 21:13:40 浏览: 105
下面是使用并查集的 Kruskal 算法解决最小生成树问题的 Python 代码:
```python
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):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.rank[px] < self.rank[py]:
self.parent[px] = py
elif self.rank[px] > self.rank[py]:
self.parent[py] = px
else:
self.parent[py] = px
self.rank[px] += 1
def kruskal(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda x: x[2])
mst = []
cost = 0
for u, v, w in edges:
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append((u, v, w))
cost += w
return mst, cost
n, e = map(int, input().split())
edges = []
for i in range(e):
n1, n2, e1 = map(int, input().split())
edges.append((n1, n2, e1))
mst, cost = kruskal(n, edges)
print("最小生成树的边:")
for u, v, w in mst:
print(u, v, w)
print("最小生成树的权值之和:", cost)
```
这里使用了一个 `UnionFind` 类来实现并查集,`kruskal` 函数则是使用 Kruskal 算法求解最小生成树。输入格式与输出格式与题目描述一致。
阅读全文