n个城市铺设通信线路,要求任意两个城市之间的通信线路是可达的(不 一定是直接可达),铺设线路的费用为城市之间的距离,试用科鲁斯卡尔算法设计该线路,使通信线路的成本最省,写出代码
时间: 2024-03-22 15:37:56 浏览: 28
以下是使用Python实现科鲁斯卡尔算法的代码:
```python
# 定义边类
class Edge:
def __init__(self, start, end, weight):
self.start = start
self.end = end
self.weight = weight
# 定义并查集
class UnionFind:
def __init__(self, n):
self.parent = list(range(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):
self.parent[self.find(i)] = self.find(j)
def connected(self, i, j):
return self.find(i) == self.find(j)
# 定义科鲁斯卡尔算法
def kruskal(n, edges):
uf = UnionFind(n)
edges.sort(key=lambda e: e.weight)
res = []
for edge in edges:
if not uf.connected(edge.start, edge.end):
uf.union(edge.start, edge.end)
res.append(edge)
return res
# 示例
n = 5
edges = [Edge(0, 1, 2), Edge(0, 2, 3), Edge(1, 2, 1), Edge(1, 3, 4), Edge(2, 3, 5), Edge(2, 4, 6), Edge(3, 4, 3)]
res = kruskal(n, edges)
for edge in res:
print(edge.start, edge.end, edge.weight)
```
其中,`Edge`表示边类,包含起点、终点和权值三个属性;`UnionFind`表示并查集类,包含`find`、`union`和`connected`三个方法;`kruskal`表示科鲁斯卡尔算法的实现函数。最后,对于一个包含n个城市的问题,输入边的列表,输出最小生成树的边列表。