最小生成树

带权连通图中边权和最小的生成树;由割性质与环性质刻画,不一定唯一。

标签 图论 / 生成树

定义

给定带权连通无向图 𝐺=(𝑉,𝐸),生成树是包含全部 𝑛 个顶点的一棵 树;等价地,它是包含全部顶点、恰好 𝑛−1 条边的连通子图。 最小生成树(Minimum Spanning Tree, MST)是所有生成树中边权和最小的那一棵。

MST 是“边的集合”层面的最优,不是“点对之间路径”层面的最优。

割性质与环性质

割性质:对任意一种把顶点分成两部分的割,横跨割的最小权边一定属于某棵 MST。

环性质:对任意一个环,环上权值最大的边一定不在某棵 MST 中;严格最大时不在任何 MST 中。

这两条性质刻画了 MST 的结构,也是所有 MST 算法的正确性基础。

唯一性

  • 若所有边权互不相同,MST 唯一。
  • 存在相同边权时,可能有多棵不同的 MST,但它们的总权值相同。

与最短路径的区别

  • MST 最小化的是所有选中边的权值和。
  • 最短路最小化的是两点之间的路径长度。
  • MST 中两点之间的唯一路径,不一定是原图中的最短路。

这是 MST 与 Dijkstra / Floyd 最常见的概念混淆。

常见误解

  • 认为 MST 唯一:边权相同可能不唯一。
  • 认为 MST 上两点路径最短:不是,见上。
  • 认为负权边会破坏 MST:MST 仍然有定义;负权影响的是最短路,不是 MST 的存在性。
  • 认为 MST 一定包含全局最短边:不一定,但一定包含横跨某个割的最短边。
源码位置