prim算法python代码

Prim算法是一种用于寻找图中最小生成树的贪心算法，它从无向加权图的一个顶点开始，逐步添加边，直到形成一棵包含所有顶点的树。以下是使用Python实现Prim算法的基本步骤：

import heapq

def prim(graph, start):
    # 初始化：设置起点的邻接权重为0，其余节点设为无穷大
    min_heap = [(0, start)]
    visited = set()
    result = {start: 0}

    while min_heap:
        current_weight, current_node = heapq.heappop(min_heap)

        if current_node not in visited:
            visited.add(current_node)
            for neighbor, weight in graph[current_node].items():
                if neighbor not in visited and (neighbor not in result or weight < result[neighbor]):
                    result[neighbor] = weight
                    heapq.heappush(min_heap, (weight, neighbor))

    return result

# 示例：邻接字典表示图，键是节点，值是字典，存储相邻节点及其权重
graph = {
    'A': {'B': 5, 'C': 4},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 4, 'B': 2, 'D': 6},
    'D': {'B': 1, 'C': 6}
}

start_node = 'A'
print(prim(graph, start_node))  # 输出最小生成树的边及其权重