最小生成树的权值怎么计算

最小生成树的权值是指连接所有顶点的边的权重之和最小的生成树的权重。具体计算方法如下：
1. 对于Prim算法，从任意一个顶点开始，每次选择一个未被访问的顶点中到已访问顶点距离最小的顶点，将其加入到已访问的顶点集合中，并将该顶点与已访问的顶点集合中的顶点相连的边的权重与当前最小边权重进行比较，更新最小边权重。重复以上步骤直到所有顶点都被访问，此时最小生成树的权值即为所有边的权重之和。
2. 对于Kruskal算法，将所有边按照权重从小到大排序，依次选择权重最小的边，如果该边的两个端点不在同一个连通块中，则将这两个端点所在的连通块合并，并将该边加入到最小生成树中。重复以上步骤直到最小生成树中包含n-1条边，此时最小生成树的权值即为所有边的权重之和。

下面是一个使用Prim算法求解最小生成树的Python代码示例：

import sys

# 以邻接矩阵的形式存储带权图
graph = [[0, 2, 4, 0, 0, 0],
         [2, 0, 2, 4, 2, 0],
         [4, 2, 0, 0, 3, 0],
         [0, 4, 0, 0, 3, 2],
         [0, 2, 3, 3, 0, 2],
         [0, 0, 0, 2, 2, 0]]

n = len(graph)  # 图的顶点数
visited = [False] * n  # 标记顶点是否已被访问
min_weight = [sys.maxsize] * n  # 记录顶点到已访问顶点集合的最小边权重
min_weight[0] = 0  # 从第一个顶点开始构建最小生成树
sum_weight = 0  # 最小生成树的权值之和

for i in range(n):
    # 选择一个未被访问的顶点中到已访问顶点距离最小的顶点
    min_index = -1
    for j in range(n):
        if not visited[j] and (min_index == -1 or min_weight[j] < min_weight[min_index]):
            min_index = j
    visited[min_index] = True
    sum_weight += min_weight[min_index]

    # 更新与新加入的顶点相连的边的权重
    for k in range(n):
        if not visited[k] and graph[min_index][k] != 0 and graph[min_index][k] < min_weight[k]:
            min_weight[k] = graph[min_index][k]

print("最小生成树的权值为：", sum_weight)