python最小生成树实例

在Python中，可以使用Prim算法或Kruskal算法来解决最小生成树问题。这里以Prim算法为例，它从无边界的图开始，每次选择当前未加入的节点中距离已连接点最近的一条边，直到所有节点都被连接起来形成一棵树。

import heapq

def prim(graph, initial_vertex):
    visited = {initial_vertex: 0}
    unvisited = [(0, initial_vertex)]
    min_heap = []

    while unvisited:
        current_weight, current_vertex = heapq.heappop(min_heap)

        if current_vertex not in visited:
            visited[current_vertex] = current_weight

        for neighbor, weight in graph[current_vertex].items():
            if neighbor not in visited:
                heapq.heappush(min_heap, (weight, neighbor))

    return visited

# 示例图的邻接字典表示（键为节点，值为字典，存储相邻节点及其权重）
graph = {
    'A': {'B': 4, 'C': 3},
    'B': {'A': 4, 'D': 5, 'E': 6},
    'C': {'A': 3, 'D': 8},
    'D': {'B': 5, 'C': 8, 'E': 7, 'F': 9},
    'E': {'B': 6, 'D': 7, 'F': 11},
    'F': {'D': 9, 'E': 11}
}

# 使用初始顶点'A'
min_cost_tree = prim(graph, 'A')
print(min_cost_tree)  # 输出最小生成树的每个节点到根的成本