问题描述：
选取具有最小权重的生成树，图G的最小生成树，包括所有顶点V及最少的边E，其中边权重最小。
要求是：每个点只需要处理一次信息，并且加起来权重最小。
image.png
解决办法：
采用贪心策略，每步沿着权重最小的边向前搜索。
代码如下：
from pythonds.graphs import PriorityQueue, Graph, Vertex
import sys
# 贪心算法
def prim(G, start):
pq = PriorityQueue()
# 把所有顶点初始化最大值
for v in G:
v.setDistance(sys.maxsize)
v.setPred(None)
start.setDistance(0)
pq.buildHeap([(v.getDistance(), v) for v in G])
while not pq.isEmpty():
currentVert = pq.delMin()
for nextVert in currentVert.getConnections():
newCost = currentVert.getWeight(nextVert)
if nextVert in pq and newCost < nextVert.getDistance():
nextVert.setPred(currentVert)
nextVert.setDistance(newCost)
pq.decreaseKey(nextVert, newCost)
