Prim算法Python实现

Prim算法是一种用于解决最小生成树问题的贪心算法。它通过逐步选择边来构建最小生成树，从而保证生成树的总权值最小。下面是Prim算法的Python实现：

def prim(graph):
    # 初始化最小生成树的集合和已访问节点的集合
    mst = []
    visited = set()

    # 选择一个起始节点
    start_node = list(graph.keys())
    visited.add(start_node)

    while len(visited) < len(graph):
        min_edge = None
        min_weight = float('inf')

        # 遍历已访问节点的集合，找到与之相连的最小权值边
        for node in visited:
            for neighbor, weight in graph[node].items():
                if neighbor not in visited and weight < min_weight:
                    min_edge = (node, neighbor)
                    min_weight = weight

        # 将找到的最小权值边加入最小生成树，并将相邻节点加入已访问节点的集合
        mst.append(min_edge)
        visited.add(min_edge)

    return mst

上述代码中，`graph`是一个字典，表示图的邻接表形式。字典的键表示节点，值是一个字典，表示与该节点相连的邻居节点及对应的边权值。函数返回一个列表，表示最小生成树的边集合。