prim算法完整代码
时间: 2023-07-03 21:10:44 浏览: 36
以下是Prim算法的完整代码实现,假设有一个无向带权图,图的点数为n,点的编号从0到n-1:
```python
import heapq
def prim(graph):
n = len(graph)
visited = [False] * n
min_heap = [(0, 0)] # 存储到生成树距离最短的点的距离和点的编号
total_weight = 0
while min_heap:
weight, node = heapq.heappop(min_heap)
if visited[node]:
continue
visited[node] = True
total_weight += weight
for neighbor, neighbor_weight in graph[node]:
heapq.heappush(min_heap, (neighbor_weight, neighbor))
return total_weight
```
在代码中,我们使用visited数组来标记每个点是否已经被加入到了生成树中,使用min_heap来存储到生成树距离最短的点的距离和点的编号,初始时将起点加入到min_heap中。然后每次从min_heap中取出距离最短的点,将其加入到生成树中,并将其所有邻接点加入到min_heap中。通过这样的方式,就可以逐步构造出最小生成树。