邻接矩阵生成Prim 算法的最小生成树代码

以下是邻接矩阵生成 Prim 算法的最小生成树代码，假设邻接矩阵用二维数组 `graph` 表示，`n` 表示节点数，`INF` 表示无穷大：

def prim(graph, n):
    # 初始化已选择节点集合和未选择节点集合
    selected = [0] * n
    selected[0] = 1
    unselected = [1] * n
    unselected[0] = 0
    
    # 初始化最小距离数组
    min_dist = graph[0]
    
    # 循环 n-1 次，每次加入一个节点到已选择节点集合中
    for i in range(n-1):
        # 从未选择节点集合中选择与已选择节点集合距离最小的节点
        min_node = -1
        min_dis = INF
        for j in range(n):
            if unselected[j] == 1 and min_dist[j] < min_dis:
                min_node = j
                min_dis = min_dist[j]
        
        # 将该节点加入已选择节点集合，并更新最小距离数组
        selected[min_node] = 1
        unselected[min_node] = 0
        for j in range(n):
            if unselected[j] == 1 and graph[min_node][j] < min_dist[j]:
                min_dist[j] = graph[min_node][j]
    
    # 计算最小生成树的权值和
    min_cost = 0
    for i in range(n):
        if selected[i] == 1:
            min_cost += min_dist[i]
    
    return min_cost

以上代码中，最小距离数组 `min_dist` 记录了已选择节点集合与未选择节点集合之间的最小距离，`selected` 和 `unselected` 分别表示已选择节点集合和未选择节点集合。在每次循环中，从未选择节点集合中选择距离最小的节点加入已选择节点集合中，并更新最小距离数组。最后计算最小生成树的权值和。