prim算法求最小生成树
时间: 2023-07-22 20:27:32 浏览: 49
Prim(普里姆)算法是一种求解带权无向图的最小生成树的算法。其基本思想是从图中任意一个点开始,每次选取与当前生成树相连的边中权值最小的边,并将其连接的点加入到生成树中,直到所有的节点都被连接。
具体实现过程如下:
1. 任选一个起始点,将其加入到已访问的节点集合中,并将该节点与其相邻的边按权值从小到大排序。
2. 从已排序的边集合中选取权值最小的边,如果该边的另一个节点未被访问,则将其加入到已访问的节点集合中,并将该边加入到生成树的边集合中。
3. 重复上述步骤,直到所有的节点都被访问。
下面是Prim算法的Python实现代码:
```python
import heapq
def prim(graph, start):
visited = set([start])
edges = [(weight, start, to) for to, weight in graph[start].items()]
heapq.heapify(edges)
mst = []
while edges:
weight, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, weight))
for to_next, weight_next in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (weight_next, to, to_next))
return mst
```
其中,graph是一个字典,表示带权无向图的邻接表,start是起始节点。返回值是一个包含每条边的起始节点、终止节点和权值的列表。