使用并查集的思想求解最小生成树问题 输入格式: n,e ;n为端点数量、m为边的数量 n1为端点1,n2为端点2, e1为边的权值 ;这样的信息有e行 输出格式: n1 n2 e1 生成树中的边的信息
时间: 2024-02-03 18:15:47 浏览: 67
以下是使用并查集的思想求解最小生成树问题的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 False
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
return True
n, e = map(int, input().split())
edges = []
for i in range(e):
n1, n2, e1 = map(int, input().split())
edges.append((n1-1, n2-1, e1))
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
mst_edges = []
for edge in edges:
if uf.union(edge[0], edge[1]):
mst_edges.append(edge)
if len(mst_edges) == n-1:
break
for edge in mst_edges:
print(edge[0]+1, edge[1]+1, edge[2])
```
其中,UnionFind类实现了并查集的基本功能,包括find和union操作。在主函数中,首先读入边的信息,并按照权值从小到大排序。然后遍历每条边,如果两个端点不在同一个连通分量中,则将它们合并,并将该边加入最小生成树的边集中。当边集中的边数等于n-1时,停止遍历,并输出最小生成树的边信息。
阅读全文