普利姆算法最小生成树

普利姆算法是一种用于求解无向图的最小生成树的基本算法。它以一个起始节点开始，每次将一个未被访问的节点加入到最小生成树集合中，并选择与该集合相邻的边中权重最小的边和它连接的未访问节点，直到最小生成树集合包含了图中的所有节点。普利姆算法的时间复杂度为O(n^2)。

以下是普利姆算法的步骤：
1. 选择一个起始节点作为最小生成树的起点。
2. 将该起始节点加入最小生成树集合，并将其标记为已访问。
3. 在所有与最小生成树集合相邻的边中，选择权重最小的边和它连接的未访问节点。
4. 将该边和节点加入最小生成树集合，并将该节点标记为已访问。
5. 重复步骤3和步骤4，直到最小生成树集合包含了图中的所有节点。

以下是Python实现普利姆算法的代码：

def prim(graph):
    # 选择一个起始节点作为最小生成树的起点
    start_node = list(graph.keys())[0]
    # 将该起始节点加入最小生成树集合，并将其标记为已访问
    visited = [start_node]
    # 初始化最小生成树的权重为0
    min_weight = 0
    # 初始化最小生成树的边为空
    min_tree = []
    # 重复步骤3和步骤4，直到最小生成树集合包含了图中的所有节点
    while len(visited) < len(graph):
        # 在所有与最小生成树集合相邻的边中，选择权重最小的边和它连接的未访问节点
        min_edge = None
        for node in visited:
            for neighbor, weight in graph[node].items():
                if neighbor not in visited:
                    if min_edge is None or weight < min_edge[2]:
                        min_edge = (node, neighbor, weight)
        # 将该边和节点加入最小生成树集合，并将该节点标记为已访问
        visited.append(min_edge[1])
        min_weight += min_edge[2]
        min_tree.append(min_edge)
    # 返回最小生成树的权重和边
    return min_weight, min_tree