最小生成树构造pirme

Prim算法是一种用于构建最小生成树的贪心算法。它的基本思想是从一个起始顶点开始，每次选择一个与当前生成树相邻的权值最小的顶点，并将其加入到生成树中，直到生成树包含了图中所有的顶点。下面是Prim算法的详细步骤：

1. 任选一个起始顶点，将其加入到生成树中。
2. 找到与当前生成树相邻的所有顶点，并计算它们与生成树中已有顶点相连的边的权值。
3. 选择权值最小的边所连接的顶点，并将其加入到生成树中。
4. 重复步骤2和步骤3，直到生成树包含了图中所有的顶点。

下面是一个使用Prim算法构建最小生成树的Python代码示例：

def prim(graph):
    # 初始化生成树和已访问顶点集合
    visited = set()
    MST = []
    # 任选一个起始顶点
    start = list(graph.keys())[0]
    visited.add(start)
    # 循环直到生成树包含了图中所有的顶点
    while len(visited) < len(graph):
        # 计算与当前生成树相邻的所有顶点的权值
        min_edge = None
        for v in visited:
            for u, w in graph[v].items():
                if u not in visited:
                    if min_edge is None or w < min_edge[2]:
                        min_edge = (v, u, w)
        # 将权值最小的边所连接的顶点加入到生成树中
        MST.append(min_edge)
        visited.add(min_edge[1])
    return MST

其中，graph是一个字典，表示带权图。字典的键是顶点，值是一个字典，表示该顶点与相邻顶点之间的边和权值。例如，下面是一个带权图的示例：

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

使用上述代码对该图进行Prim算法求解，可以得到最小生成树为：

[('A', 'B', 2), ('B', 'D', 1), ('D', 'C', 5)]