最小生成树prim算法python实现

最小生成树（Minimum Spanning Tree, MST）是指在一个加权无向图中找到一棵包含所有顶点的树，其总边权重尽可能小。Prim算法是一种常用的求解MST的贪心算法，它的基本思想是从某个顶点开始，每次选择与当前已选节点相连、且未加入集合的最短边，逐步添加新的节点直到覆盖所有节点。

以下是Python实现Prim算法的一个简单版本：

import heapq

def prim(graph, start):
    n = len(graph)
    visited = [False] * n
    dist = [float('inf')] * n
    dist[start] = 0
    edges = []

    for _ in range(n - 1):
        min_dist = float('inf')
        u = None
        for i in range(n):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                u = i
        visited[u] = True
        for v, weight in graph[u]:
            if not visited[v] and weight < dist[v]:
                dist[v] = weight
                edges.append((u, v, weight))

    return edges, dist

# 示例图结构（邻接权重字典）
graph = {
    0: [(1, 4), (2, 8)],
    1: [(0, 4), (3, 7), (2, 6)],
    2: [(0, 8), (1, 6), (3, 9)],
    3: [(1, 7), (2, 9), (4, 5)],
    4: [(0, 4), (3, 5)]
}

start_node = 0
result = prim(graph, start_node)
print(f"最小生成树边的列表: {result[0]}")
print(f"每个顶点到起点的距离: {result[1]}")