给定下图,其最小生成树的总权重是 QQ20190620-220532@2x.png
时间: 2023-07-22 14:09:21 浏览: 251
使用 Prim 算法或 Kruskal 算法可以求解该图的最小生成树。
以下是使用 Kruskal 算法求解该图的最小生成树的步骤:
1. 将所有边按照权值从小到大排序。
2. 从权值最小的边开始,依次将每条边加入最小生成树中。如果加入该边后会形成环,则舍弃该边。
3. 重复步骤 2,直到最小生成树包含 n-1 条边(n 为图中的顶点数)。
按照上述步骤,可以得到如下最小生成树:
```
1 -- 2 -- 4
|
3
```
加入到最小生成树中的边依次是 13, 12, 24。因此,最小生成树的总权重是 13 + 12 + 24 = 49。因此,答案为 49。
阅读全文