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 = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}

mst = prim(graph)
print(mst)

这段代码将输出最小生成树的边集合。你可以根据需要进行进一步的处理或输出。