生成最小的树python源码prim算法

下面是使用 Prim 算法生成最小生成树的 Python 代码：

import heapq

def prim(graph):
    # 选取一个起点
    start_node = list(graph.keys())[0]
    mst = set([start_node])
    edges = []

    # 将起点的所有边加入堆中
    for neighbor, weight in graph[start_node].items():
        heapq.heappush(edges, (weight, start_node, neighbor))

    # 重复选择一条最小边，并将其加入最小生成树中
    while edges:
        weight, n1, n2 = heapq.heappop(edges)
        if n2 not in mst:
            mst.add(n2)
            for neighbor, weight in graph[n2].items():
                if neighbor not in mst:
                    heapq.heappush(edges, (weight, n2, neighbor))

    return mst

其中，`graph` 是一个字典，表示无向图的邻接表。例如，如果有一条边 (1, 2) 权重为 3，那么可以表示为：

graph = {
    1: {2: 3},
    2: {1: 3},
}

函数返回一个集合，表示最小生成树中的所有节点。