Python写代码:使用并查集的思想求解最小生成树问题。输入格式: n,e ,其中n表示端点数量、m边的数量; n1,n2,e1 ,其中n1端点1,n2端点2 e1边的权值; 。。。 ;这样的信息有e行 。输出格式: n1 n2 e1 生成树中的边的信息
时间: 2024-02-27 20:51:46 浏览: 26
好的,下面是Python代码实现:
```python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
x, y = self.find(i), self.find(j)
if x == y:
return False
if self.rank[x] < self.rank[y]:
x, y = y, x
self.parent[y] = x
if self.rank[x] == self.rank[y]:
self.rank[x] += 1
return True
def kruskal(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda x: x[2])
result = []
for u, v, w in edges:
if uf.union(u, v):
result.append((u, v, w))
return result
if __name__ == '__main__':
n, e = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(e)]
mst = kruskal(n, edges)
for u, v, w in mst:
print(u, v, w)
```
其中,`UnionFind`类实现了并查集的基本操作,`kruskal`函数采用Kruskal算法求解最小生成树,最后输出生成树中的边的信息。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)