Prim算法有这一篇就够啦
from collections import defaultdict
from heapq import heapify, heappop, heappush
def prim(map,start):
#最小生成树
mst = []
#存已连接点集合
city = {start}
#存待走边集合
next = map[start]#
#待走边排序
heapify(next)#按距离建立小顶堆
while next:
#取出最小边
distance, head, tail = heappop(next)
#如果下个路口没走过
if tail not in city:
#加入已连接集合
city.add(tail)
#加入最小生成树
mst.append((head, tail, distance))
# 没走过的相邻边加入
for e in map[tail]:
if e[2] not in city:
heappush(next, e)
if len(mst)
代码前面能有相关的说明对新手更友好一些。