自来水管道维修Prim算法代码
时间: 2024-06-15 22:07:26 浏览: 14
Prim算法是一种用于解决最小生成树问题的贪心算法。它通过逐步选择边来构建最小生成树,从而保证生成的树具有最小的权值和。下面是Prim算法的代码实现:
```python
def prim(graph):
# 初始化最小生成树集合和已访问节点集合
mst = []
visited = set()
# 选择一个起始节点
start_node = list(graph.keys())[0]
visited.add(start_node)
while len(visited) < len(graph):
min_edge = None
min_weight = float('inf')
# 遍历已访问节点集合中的节点
for node in visited:
# 遍历与当前节点相连的边
for neighbor, weight in graph[node].items():
# 如果相邻节点未被访问且权值更小,则更新最小边和权值
if neighbor not in visited and weight < min_weight:
min_edge = (node, neighbor)
min_weight = weight
# 将最小边加入最小生成树集合,并将相邻节点加入已访问节点集合
mst.append(min_edge)
visited.add(min_edge[1])
return mst
```
上述代码中,`graph`是一个字典,表示图的邻接表形式。字典的键表示节点,值是一个字典,表示与该节点相连的边及其权值。函数返回一个列表,表示最小生成树中的边。