最小生成树prim算法实现

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

INF = 0x3f3f3f3f

def prim(graph):
    n = len(graph)
    # 初始化距离数组和访问数组
    dist = [INF] * n
    visited = [False] * n
    # 从第一个节点开始
    dist[0] = 0
    for i in range(n):
        # 找到距离最小的未访问节点
        u = -1
        for j in range(n):
            if not visited[j] and (u == -1 or dist[j] < dist[u]):
                u = j
        # 标记为已访问
        visited[u] = True
        # 更新与u相邻节点的距离
        for v in range(n):
            if not visited[v] and graph[u][v] != INF and graph[u][v] < dist[v]:
                dist[v] = graph[u][v]
    # 返回最小生成树的边权值之和
    return sum(dist)

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