最小生成树普里姆算法

普里姆算法是一种用于构建最小生成树的贪心算法。它从一个源节点开始，逐步扩展生成树，直到覆盖所有节点。具体步骤如下：

1. 选择一个起始节点，并将其加入生成树中。
2. 找到与生成树相邻的所有边，并选择其中权重最小的边所连接的节点。
3. 将该节点加入生成树中，并将该边加入生成树的边集中。
4. 重复步骤2和3，直到生成树包含所有节点。

下面是一个使用Python实现普里姆算法的例子：

def prim(graph):
    # 选择一个起始节点
    start_node = list(graph.keys())[0]
    # 初始化生成树和已访问节点集合
    visited = set([start_node])
    mst = []
    # 当已访问节点集合不包含所有节点时
    while len(visited) < len(graph):
        # 找到与生成树相邻的所有边
        edges = []
        for node in visited:
            for neighbor, weight in graph[node].items():
                if neighbor not in visited:
                    edges.append((node, neighbor, weight))
        # 选择权重最小的边所连接的节点
        min_edge = min(edges, key=lambda x: x[2])
        # 将该节点加入生成树中，并将该边加入生成树的边集中
        mst.append(min_edge)
        visited.add(min_edge[1])
    return mst

其中，`graph`是一个字典，表示无向图的邻接表。例如，对于以下无向图：

  2 - 3
 /   / \
1 - 4 - 5

可以表示为：

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

调用`prim(graph)`函数即可得到该图的最小生成树。