prim算法python
时间: 2023-07-10 21:08:56 浏览: 45
下面是Python实现的Prim算法:
```python
from queue import PriorityQueue
def prim(graph, start):
visited = set()
pq = PriorityQueue()
visited.add(start)
for neighbor, weight in graph[start].items():
pq.put((weight, start, neighbor))
while not pq.empty():
weight, frm, to = pq.get()
if to not in visited:
visited.add(to)
for neighbor, weight in graph[to].items():
if neighbor not in visited:
pq.put((weight, to, neighbor))
return visited
```
其中,`graph`是一个字典,表示图,`start`是起始节点。算法使用了优先队列来实现最小生成树的构建。具体实现过程如下:
1. 将起始节点加入已访问集合。
2. 将起始节点的邻居节点与边权值加入优先队列。
3. 从优先队列中取出最小权值的边,如果该边的终点未被访问,则将该节点加入已访问集合,并将该节点的邻居节点与边权值加入优先队列。
4. 重复步骤3,直到优先队列为空。
最终返回visited,即为最小生成树上的所有节点。