数据结构与算法 / 系统课时
最小生成树问题
最小生成树问题
本课从“如何用最少总代价连接所有顶点”出发,建立最小生成树的概念框架,并用割、轻边和安全边解释局部选择为何能够保持全局最优,为后续 Kruskal 算法提供判断依据。
学习目标
- 区分生成树、最小生成树与普通最短路径问题。
- 理解割、跨割边、轻边和安全边之间的关系。
- 能够检查候选边是否满足最小生成树的安全边性质。
问题与核心概念
给定一个连通、无向、带权图 ,目标是选择一组边,使所有顶点保持连通、选中边不形成环,并让边权总和最小。满足“连通且无环”的子图称为生成树;权重总和最小的生成树称为最小生成树。
一棵含有 个顶点的生成树必然恰好包含 条边。少于这个数量时无法连接所有顶点,多于这个数量时至少形成一个环。最小生成树优化的是整棵树的总权重,不是某个源点到其他顶点的路径长度,因此它与最短路径树解决的是不同问题。
当边权存在重复值时,一个图可能拥有多棵不同的最小生成树;只要它们的总权重都达到最小,就都是合法答案。若图不连通,则不存在覆盖全部顶点的生成树,只能分别得到各连通分量的最小生成森林。
割、轻边与安全边
割把顶点集合划分为两个互不相交且都非空的部分,例如 与 。一条边的两个端点分属割的两侧时,这条边称为跨割边。跨越同一个割的边中,权重最小的边称为轻边;若有多条边并列最小,它们都可以被视为轻边。

安全边不是单纯指“权重很小的边”,而是指把它加入当前边集后,当前选择仍然能够扩展成某棵最小生成树。割性质给出了常用判定:设当前已选边集 已包含在某棵最小生成树中;若一个割尊重 ,也就是 中没有边跨越该割,那么该割上的任意轻边对 都是安全的。
这个结论可以用交换思想理解。假设某棵最小生成树没有包含选定轻边,把轻边加入后会形成唯一环;该环必然还有另一条边跨越同一割。因为轻边权重不大于那条边,删除后者不会增加总权重,得到的仍是一棵最小生成树。因此,选择轻边不会破坏最优性。
判定过程与边界
检查一条候选边时,可以按以下顺序思考:
- 当前已选边是否保持无环,并且可以包含在某棵最小生成树中。
- 能否找到一个尊重当前边集的割。
- 候选边是否跨越该割。
- 候选边是否是该割上的最小权重边之一。
- 加入后是否仍保持无环;若形成环,说明当前割或候选边的选择不符合构造过程。
容易混淆的一点是:图中全局最轻的边一定安全,但之后每一步不必继续选择“尚未使用边中的全局最轻边”。真正需要的是当前某个合法割上的轻边。Kruskal 算法通过并查集维护连通分量,让每条连接不同分量的最轻边自动对应一个合法割。
练习
- 给定顶点集合
{A,B,C,D}和边A-B:1、A-C:3、B-C:2、B-D:4、C-D:5,找出割{A,B}与{C,D}上的全部跨割边和轻边,并说明轻边为何安全。 - 构造一个含有重复边权、且存在两棵不同最小生成树的无向连通图。验收条件是两棵树都包含 条边、均无环且总权重相同。
本课总结
- 生成树以 条边连接全部顶点且不形成环,最小生成树进一步最小化总权重。
- 割性质把全局最优问题转化为可验证的局部选择:尊重当前边集的割上,轻边是安全边。
- 图不连通时只能得到最小生成森林;重复边权可能产生多棵同权最优生成树。
下一课预告
下一课将学习“Kruskal 算法”,把安全边性质落实为“边排序 + 并查集”的可运行实现,并验证如何高效跳过会形成环的边。