构造使n个城市相连的最小生成树,要求:写出代码
时间: 2023-07-22 14:19:30 浏览: 49
好的,这个问题我可以回答。构造 n 个城市相连的最小生成树可以使用 Kruskal 算法或 Prim 算法来实现。下面是一个使用 Kruskal 算法的 Python 代码示例:
``` 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)
ans = []
for edge in edges:
if uf.union(edge.u, edge.v):
ans.append(edge)
if len(ans) == n - 1:
break
return ans
# 测试样例
n = 5
edges = [Edge(0,1,2), Edge(0,3,6), Edge(1,2,3), Edge(1,3,8), Edge(1,4,5), Edge(2,4,7), Edge(3,4,9)]
ans = kruskal(n, edges)
for edge in ans:
print(edge.u, edge.v, edge.w)
```
这个代码实现了 Kruskal 算法,它的时间复杂度为 $O(m \log m)$,其中 $m$ 表示边的数量。