# -*- coding: utf-8 -*-
# @Time : 2019/5/25 12:31
# @Author : WHS
# @FileName: text.py
# @Software: PyCharm
# @Python Version：3.6.0
from collections import defaultdict
from heapq import heapify,heappop,heappush
#heappush（入堆）、heappop（出堆）、heapify（创建堆）
def Prim(nodes,edges):
#无向图
conn = defaultdict(list)
for n1,n2,c in edges:
conn[n1].append((c,n1,n2))
conn[n2].append((c,n2,n1))
#print(conn)
mst = []
used = set(nodes[0]) #已访问过的顶点
usable_edges = conn[nodes[0]]
heapify(usable_edges) #建堆
while usable_edges:
cost, n1, n2 = heappop(usable_edges) #权重 顶点 找出权重最小的边
if n2 not in used: #顶点n2没有被访问
used.add(n2) #将n2加入到已访问集合
mst.append((n1, n2, cost)) #存储过程
for e in conn[n2]: #遍历顶点n2能到达的顶点
if e[2] not in used: #如果顶点n2能到达的顶点不在已访问顶点集合中，则加入其能到达的边
heappush(usable_edges, e)
return mst
nodes = list("ABCDEFG")
edges = [ ("A", "B", 7), ("A", "D", 5),
("B", "C", 8), ("B", "D", 9),
("B", "E", 7), ("C", "E", 5),
("D", "E", 15), ("D", "F", 6),
("E", "F", 8), ("E", "G", 9),
("F", "G", 11)]
print(Prim(nodes,edges))
原文
