7.9图的应用：最小生成树

最小生成树：Prim算法

❖解决最小生成树问题的Prim算法，属于“贪心算法”，即每步都沿着最小权重的边向前搜索。
❖构造最小生成树的思路很简单，如果T还不是生成树，则反复做：找到一条最小权重的可以安全添加的边，将边添加到树T
❖“可以安全添加”的边，定义为一端顶点在树中，另一端不在树中的边，以便保持树的无圈特性

Prim 算法的应用过程

# 最小生成树prim算法
# G - 无向赋权图
# start - 开始节点
# 返回从开始节点创建最小生成树
def prim(G, start):
    pq = PriorityQueue()  # 创建优先队列
    start.setDistance(0)  # 起点最小权重代价设置为0，其它节点最小权重代价默认maxsize
    # 将节点排入优先队列，start在最前面
    pq.buildHeap([(v.getDistance(), v) for v in G])
    while not pq.isEmpty():
        # 取距离*已有树*最小权重代价的节点出队列，作为当前节点
        # 当前节点已解出最小生成树的前驱pred和对应最小权重代价dist
        currentVert = pq.delMin()
        # 遍历节点的所有邻接节点
        for nextVert in currentVert.getConnections():
            # 从当前节点出发，逐个检验到邻接节点的权重
            newCost = currentVert.getWeight(nextVert)
            # 如果邻接节点是"安全边"，并且小于邻接节点原有最小权重代价dist，就更新邻接节点
            if nextVert in pq and newCost < nextVert.getDistance():
                # 更新最小权重代价dist
                nextVert.setPred(currentVert)
                # 更新返回路径
                nextVert.setDistance(newCost)
                # 更新优先队列
                pq.decreaseKey(nextVert, newCost)