最小生成树

---

特征：

1. 其边数等于顶点数-1，且树内一定不会有环
2. 对给定的图，最小生成树可以不唯一，但是其边权之和是唯一且最小的。
3. 根节点不唯一，看题目要求。

---

相关算法：

1. prim算法
2. kruskal算法

两种算法的取舍：

如果是稠密图（边多），则使用prim算法。如果稀疏图（边少），则用kruskal算法。因为kruskal需要进行边的排序，开销主要在排序这边。