普里姆算法最小生成树完整代码

普里姆算法（Prim's Algorithm）是一种用于求解无向加权图中最小生成树的经典算法，它从一个顶点开始，每次选择与当前生成树相连的边中权重最小的一条，直到所有顶点都被包含在内。以下是用Python实现的简单版本的普里姆算法：

import heapq

def prim(graph, start):
    # 初始化：设置起点到所有顶点的距离为无穷大，除了起点是0
    distances = {v: float('infinity') for v in graph}
    distances[start] = 0
    visited = set()
    edges = []

    # 使用优先队列存储待访问的边
    pq = [(0, start)]

    while pq:
        # 从优先队列中获取当前最小距离的边
        current_distance, current_vertex = heapq.heappop(pq)

        # 如果当前节点已访问过，跳过
        if current_vertex in visited:
            continue

        # 标记当前节点为已访问
        visited.add(current_vertex)

        # 遍历当前节点的所有邻居
        for neighbor, weight in graph[current_vertex].items():
            # 如果经过当前节点到邻居的路径比已知的更短
            new_distance = current_distance + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                # 将更优的边加入优先队列
                heapq.heappush(pq, (new_distance, neighbor))

                # 添加边到结果集合
                edges.append((current_vertex, neighbor, weight))

    return distances, edges

# 示例图数据
graph = {
    'A': {'B': 3, 'C': 1},
    'B': {'A': 3, 'C': 2, 'D': 4},
    'C': {'A': 1, 'B': 2, 'D': 5},
    'D': {'B': 4, 'C': 5, 'E': 6},
    'E': {'D': 6}
}

start = 'A'  # 选择起始节点
distances, edges = prim(graph, start)
print("最小生成树距离:", distances)
print("最小生成树边:", edges)