最小生成树 权值如何求

1. 克鲁斯卡尔算法（Kruskal's Algorithm）：

将所有边按照权值从小到大排序。

初始化一个空森林，其中每个顶点都是一个单独的树。

遍历排序后的边，如果当前边连接的两个顶点属于不同的树，则将这条边添加到森林中，否则跳过。

2. 普里姆算法（Prim's Algorithm）：

创建一个优先队列（最小堆），用于存储与已选顶点相连的边，并按照权值排序。

当优先队列不为空时，取出权值最小的边。

在两种算法中，权值的计算方法都是基于边的权值。边的权值通常由问题本身给出，例如在图论问题中，每条边可以表示连接两个顶点的距离、成本或其他度量。

克鲁斯卡尔算法：

1. 将所有边按权值排序。

3. 遍历排序后的边，对于每条边：

检查这条边是否将两个不同的连通分量连接起来。

如果是，将这条边添加到`MST`中。

4. 输出`MST`中的所有边，并计算它们的权值之和。

普里姆算法：

2. 创建一个优先队列，初始化为起点与相邻顶点的边，并按权值排序。

3. 当优先队列不为空时：

取出权值最小的边。