最小生成树 python prim

Prim算法是一种常用的最小生成树算法，以下是一个Python实现的Prim算法。

def prim(graph):
    """Prim算法实现最小生成树"""
    # 选取一个起始点
    start_node = list(graph.keys())[0]
    # 初始时所有点都不在最小生成树中
    in_tree = set([start_node])
    # 用来记录边的权值
    edges = []
    # 用来记录最小生成树的总权值
    total_weight = 0
    # 重复进行以下步骤，直到所有点都在最小生成树中
    while len(in_tree) < len(graph):
        # 选取一个跨越最小生成树和不在最小生成树中的边的权值最小的边
        min_edge = None
        min_weight = float('inf')
        for node in in_tree:
            for neighbor, weight in graph[node].items():
                if neighbor not in in_tree and weight < min_weight:
                    min_edge = (node, neighbor)
                    min_weight = weight
        # 将该边加入最小生成树中
        edges.append(min_edge)
        total_weight += min_weight
        in_tree.add(min_edge[1])
    return edges, total_weight

其中，`graph`参数是一个字典，表示图中的节点和边。字典的键表示节点，字典的值是另一个字典，表示与该节点相连的所有边和权值。

例如，以下是一个简单的图的表示：

graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1},
    'C': {'A': 3, 'B': 1, 'D': 4},
    'D': {'C': 4}
}

表示节点A与节点B和节点C相连，边权分别为2和3；节点B与节点A和节点C相连，边权分别为2和1；节点C与节点A、节点B和节点D相连，边权分别为3、1和4；节点D与节点C相连，边权为4。