算法理论基础
最小生成树两大理论基础：1. 切分性质：任意割的权值最小割边，必属于某棵最小生成树，是 Prim 算法的依据。2. 环性质：任意环中权值最大的边，一定不在最小生成树里，支撑 Kruskal 算法。连通加权无向图才存在最小生成树，总权值和唯一，可有多棵不同最小生成树。
最小生成树问题1分钟阅读
最小生成树（MST）之所以能够使用 Prim 或 Kruskal 这样直观的贪心算法求解，并且保证最终结果一定是全局最优解，其核心建立在图论中严格的割（Cut）与环（Cycle）性质之上。
理解 MST 理论基础的前提是掌握以下两个概念：
- 割（Cut）：指将图的顶点集 划分为两个互不相交的非空子集 的一种划分。
- 横跨边（Cross Edge）：如果一条边 的一个端点 ，另一个端点 ，则称该边为横跨割 的横跨边。
所有求解 MST 的贪心算法，其正确性均可由以下三大定理推导证明：
- 内容：对于无向图中的任意一个割 ，如果边 是所有横跨该割的横跨边中权值最小的一条（即轻量边/Light Edge），那么边 一定属于图的某棵最小生成树。如果图中所有边权值均互不相同，则边 必定存在于唯一的最小生成树中。
- 理论意义：Prim 算法的直接数学依据。Prim 算法每次将已选节点集合作为 ，未选节点集合作为 ，贪心选择连接两集合的最短边，就是利用了切分定理。
- 内容：在无向图的任意一个简单环（Cycle）中，权值最大的那条边绝不可能属于该图的任何一棵最小生成树。
- 理论意义：Kruskal 算法判环与避环的直接依据。如果一条边与已选择的边构成了环，且它是环上最大的边，就可以安全地舍弃。
- 最优子结构：最小生成树问题具备最优子结构。若将 MST 中的任意一条边 切断，生成树会被分为两棵子树 和 。则 必是对应子图的最小生成树， 也必是对应子图的最小生成树。
- 算法统一性：无论是“按点生长”（Prim）还是“按边合并”（Kruskal），都是在维持无环特性的前提下，不断利用割性质选择安全边（Safe Edge）加入集合，直到选满 条边。
为直观展示其严密性，这里用反证法（替换法）对切分定理进行简要证明：
证明目标：横跨割 的最小横跨边 必定属于某棵最小生成树 。
- 假设：假设不存在包含边 的最小生成树。现有一棵不包含边 的最小生成树 。
- 构环：将边 加入到 中。由于 是树，加入边 后必定会产生一个包含 的简单环 。
- 找替换边：因为 跨越了割 ，而环 是闭合的，所以环上必有另一条边 同样跨越了割 。
- 替换构造：我们将 从树中删去，用 替代它，得到一个新的生成树 。
- 推导矛盾：
- 新生成树的总权值为：。
- 因为 是横跨该割的最小边，所以 。
- 这意味着 。
- 如果 ，则 ，这与 是最小生成树相矛盾！
- 如果 ，则 ，说明存在包含 的最小生成树 。
结论：假设不成立，最小横跨边 必定可以属于某棵最小生成树。
- 充分条件：如果无向连通图中的所有边的权值均互不相同，则该图的最小生成树是唯一的。
- 存在多解的情况：当图中存在多条权值相同的边时，在割或环的选择中可能会产生等价替换，从而导致该图可能存在多棵不同的最小生成树，但所有最小生成树的边权总和必然完全相等。