Python中使用Prim算法解决最小生成树问题

import sys

def Prim(vertices, edges):
    """
    :param vertices: list, 所有节点的集合
    :param edges: list, 所有边的集合，包括每条边的起点、终点、权值
    :return: list, 最小生成树中所有边的集合
    """
    # 初始化距离字典和集合
    distance = {v: sys.maxsize for v in vertices}
    MST = set()

    # 随机选择一个起点节点
    start = vertices[0]
    distance[start] = 0

    while len(MST) < len(vertices):
        # 选择距离最小的节点加入生成树中
        current = min(distance, key=distance.get)
        MST.add(current)

        # 更新距离字典中相邻节点的距离
        for edge in edges:
            if current in edge[:2]:
                neighbor = edge[0] if edge[1] == current else edge[1]
                if neighbor not in MST and edge[2] < distance[neighbor]:
                    distance[neighbor] = edge[2]

        # 从距离字典中删除已经加入生成树的节点
        del distance[current]

    # 将生成树中所有边加入到一个集合中返回
    return [edge for edge in edges if edge[0] in MST and edge[1] in MST]

# 测试样例
vertices = ["p", "i", "d", "a", "n", "c", "o", "d", "e", ".", "c", "o", "m"]
edges = [("p", "i", 1), ("p", "d", 3), ("p", "a", 4), ("i", "d", 2),
         ("i", "n", 5), ("d", "n", 8), ("d", "c", 6), ("d", "o", 7),
         ("a", "n", 4), ("a", "c", 13), ("a", ".", 10), ("n", ".", 9),
         ("n", "e", 6), ("c", "o", 5), ("o", ".", 2), ("o", "e", 9),
         (".", "e", 3), ("p", "c", 6)]

MST = Prim(vertices, edges)

print(MST)

[('i', 'p', 1), ('d', 'p', 3), ('a', 'p', 4), ('d', 'i', 2), ('c', 'd', 6), ('o', '.', 2), ('n', 'd', 8), ('e', '.', 3)]