最小生成树

生成树包含图中全部顶点，并在这些顶点之间保持连通且无环；对V个顶点，恰好有V减一条边。最小生成树在所有这类树中比较边权之和，选取总权重最小者，而不是分别让每条保留边都成为全图最小边。

权重可以表示连接成本，不必是真实几何距离，也可以为零或负数。若原图不连通，就不存在覆盖全部顶点的单棵生成树；可以改为为每个连通分量求一棵最小生成树，整体称为最小生成森林。

参考：[1] [2]

一个割把顶点分成两个互不相交的集合，跨割边连接两边。把已有选择保持在各自一侧时，选一条最轻跨割边可以安全扩展某棵最优生成树；这为Prim和Kruskal等贪心方法提供了证明基础。

若所有权重互异，最小生成树唯一，最轻跨割边的归属也更直接。存在并列权重时，可能有多棵同成本答案，算法仍可正常工作，但不能把某次选中的同权边写成所有最优树都必须包含的唯一边。

参考：[1] [3]

最短路径树要求从一个指定源点到其他顶点的路径尽量短，最小生成树则使整棵树边权之和最小。共享某些连接可以节省总边成本，却使个别顶点间的绕行变长，因此两个目标通常不会得到同一棵树。

实际网络可能还要求冗余、带宽或故障后连通。树删除任一条边就会断开，最小生成树不会自动满足这些可靠性约束。把它用于设计时，应先确认问题确实允许无冗余树结构，再解释成本结果的适用范围。

参考：[1]