数据结构与算法 / 系统课时

最小生成树问题

最小生成树问题

本课从“如何用最少总代价连接所有顶点”出发,建立最小生成树的概念框架,并用割、轻边和安全边解释局部选择为何能够保持全局最优,为后续 Kruskal 算法提供判断依据。

学习目标

  • 区分生成树、最小生成树与普通最短路径问题。
  • 理解割、跨割边、轻边和安全边之间的关系。
  • 能够检查候选边是否满足最小生成树的安全边性质。

问题与核心概念

给定一个连通、无向、带权图 G=(V,E)G=(V,E),目标是选择一组边,使所有顶点保持连通、选中边不形成环,并让边权总和最小。满足“连通且无环”的子图称为生成树;权重总和最小的生成树称为最小生成树。

一棵含有 ∣V∣|V| 个顶点的生成树必然恰好包含 ∣V∣−1|V|-1 条边。少于这个数量时无法连接所有顶点,多于这个数量时至少形成一个环。最小生成树优化的是整棵树的总权重,不是某个源点到其他顶点的路径长度,因此它与最短路径树解决的是不同问题。

当边权存在重复值时,一个图可能拥有多棵不同的最小生成树;只要它们的总权重都达到最小,就都是合法答案。若图不连通,则不存在覆盖全部顶点的生成树,只能分别得到各连通分量的最小生成森林。

割、轻边与安全边

割把顶点集合划分为两个互不相交且都非空的部分,例如 SS 与 V−SV-S。一条边的两个端点分属割的两侧时,这条边称为跨割边。跨越同一个割的边中,权重最小的边称为轻边;若有多条边并列最小,它们都可以被视为轻边。

割、轻边与安全边关系

安全边不是单纯指“权重很小的边”,而是指把它加入当前边集后,当前选择仍然能够扩展成某棵最小生成树。割性质给出了常用判定:设当前已选边集 AA 已包含在某棵最小生成树中;若一个割尊重 AA,也就是 AA 中没有边跨越该割,那么该割上的任意轻边对 AA 都是安全的。

这个结论可以用交换思想理解。假设某棵最小生成树没有包含选定轻边,把轻边加入后会形成唯一环;该环必然还有另一条边跨越同一割。因为轻边权重不大于那条边,删除后者不会增加总权重,得到的仍是一棵最小生成树。因此,选择轻边不会破坏最优性。

判定过程与边界

检查一条候选边时,可以按以下顺序思考:

  1. 当前已选边是否保持无环,并且可以包含在某棵最小生成树中。
  2. 能否找到一个尊重当前边集的割。
  3. 候选边是否跨越该割。
  4. 候选边是否是该割上的最小权重边之一。
  5. 加入后是否仍保持无环;若形成环,说明当前割或候选边的选择不符合构造过程。

容易混淆的一点是:图中全局最轻的边一定安全,但之后每一步不必继续选择“尚未使用边中的全局最轻边”。真正需要的是当前某个合法割上的轻边。Kruskal 算法通过并查集维护连通分量,让每条连接不同分量的最轻边自动对应一个合法割。

练习

  1. 给定顶点集合 {A,B,C,D} 和边 A-B:1、A-C:3、B-C:2、B-D:4、C-D:5,找出割 {A,B} 与 {C,D} 上的全部跨割边和轻边,并说明轻边为何安全。
  2. 构造一个含有重复边权、且存在两棵不同最小生成树的无向连通图。验收条件是两棵树都包含 ∣V∣−1|V|-1 条边、均无环且总权重相同。

本课总结

  • 生成树以 ∣V∣−1|V|-1 条边连接全部顶点且不形成环,最小生成树进一步最小化总权重。
  • 割性质把全局最优问题转化为可验证的局部选择:尊重当前边集的割上,轻边是安全边。
  • 图不连通时只能得到最小生成森林;重复边权可能产生多棵同权最优生成树。

下一课预告

下一课将学习“Kruskal 算法”,把安全边性质落实为“边排序 + 并查集”的可运行实现,并验证如何高效跳过会形成环的边。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最小生成树问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通