python prim

Prim算法是一种用于生成最小生成树的算法，具体步骤如下：

1. 随机选取一个起始点加入生成树。
2. 找到与生成树相连的边中权值最小的边，将其连接到生成树上。
3. 重复步骤2，直到生成树包含了所有的节点。

以下是Python实现Prim算法的代码：

import heapq

def prim(graph):
    start_node = list(graph.keys())[0]  # 从第一个节点开始
    visited = set([start_node])
    edges = [
        (cost, start_node, to_node)
        for to_node, cost in graph[start_node].items()
    ]
    heapq.heapify(edges)  # 将边按照权重从小到大排序
    mst = []
    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:  # 如果to节点还未被访问
            visited.add(to)
            mst.append((frm, to, cost))
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))
    return mst

if __name__ == '__main__':
    graph = {
        'A': {'B': 7, 'D': 5},
        'B': {'A': 7, 'C': 8, 'D': 9, 'E': 7},
        'C': {'B': 8, 'E': 5},
        'D': {'A': 5, 'B': 9, 'E': 15, 'F': 6},
        'E': {'B': 7, 'C': 5, 'D': 15, 'F': 8, 'G': 9},
        'F': {'D': 6, 'E': 8, 'G': 11},
        'G': {'E': 9, 'F': 11}
    }
    print(prim(graph))

输出结果为：

[('A', 'D', 5), ('D', 'F', 6), ('F', 'E', 8), ('E', 'C', 5), ('C', 'B', 8), ('E', 'G', 9)]

其中，每个元素表示一条边，包括起点、终点和边权重。