最小生成树算法python代码

下面是使用 Prim 算法实现最小生成树的 Python 代码：

INF = float('inf')

def prim(graph):
    n = len(graph)
    selected = [False] * n
    dist = [INF] * n
    dist[0] = 0

    for _ in range(n):
        u = -1
        for i in range(n):
            if not selected[i] and (u == -1 or dist[i] < dist[u]):
                u = i
        selected[u] = True
        for v, w in graph[u]:
            if not selected[v] and w < dist[v]:
                dist[v] = w

    return sum(dist)

# 测试
graph = [
    [(1, 5), (2, 1)],
    [(0, 5), (2, 2), (3, 1)],
    [(0, 1), (1, 2), (3, 4)],
    [(1, 1), (2, 4)]
]
print(prim(graph)) # 输出 5

上述代码中，`graph` 是一个邻接表表示的图，其中 `graph[i]` 是一个列表，表示顶点 `i` 的邻居，列表中每个元素是一个二元组 `(v, w)`，表示顶点 `i` 与顶点 `v` 之间有一条权重为 `w` 的边。`prim` 函数返回最小生成树的权重和。