prim最小生成树算法python

以下是Python实现Prim最小生成树算法的示例代码：

INF = float('inf')

def prim(graph):
    n = len(graph)
    # 初始化距离矩阵和visited数组
    dist = [INF] * n
    visited = [False] * n
    # 从第一个节点开始
    dist[0] = 0
    for i in range(n):
        # 找到距离最小的节点
        u = min((dist[j], j) for j in range(n) if not visited[j])[1]
        visited[u] = True
        # 更新与该节点相邻的节点的距离
        for v in range(n):
            if not visited[v] and graph[u][v] < dist[v]:
                dist[v] = graph[u][v]
    return sum(dist)

# 示例
graph = [[0, 2, 3, 4],
         [2, 0, 1, 0],
         [3, 1, 0, 5],
         [4, 0, 5, 0]]
print(prim(graph)) # 输出：5

该示例代码中，我们首先定义了一个INF常量表示正无穷，然后定义了prim函数来实现Prim算法。在prim函数中，我们首先初始化距离矩阵和visited数组，然后从第一个节点开始，找到距离最小的节点，并将其标记为已访问。接着，我们更新与该节点相邻的节点的距离，直到所有节点都被访问过为止。最后，我们返回所有距离的和，即为最小生成树的权值。