最小生成树的算法如Prim算法、Kruskal算法均为贪心算法，其中Prim算法是对图上的节点贪心，而Kruskal算法是对图上的边贪心。

理论基础

  • 最小生成树的形状不唯一，但权值和一定唯一！
  • 任意一棵最小生成树一定可以包含无向图中权值最小的边，不是一定包含。

证明：若最小生成树没有包含最小边，则添加最小边后构成的环上其余边权一定大于等于最小边，故替换掉其中某一条，仍然是最小生成树。

  • 给定一张无向图G = (V, E), n = |V|, m = |E|。从E中选出k < n - 1条边构成G的一个生成森林。如果再从剩余的m - k条边中选n - 1 - k条边添加到生成森林中使其称为G的生成树，并且选出的边的权值之和最小，则该生成树一定可以包含m - k条边中连接生成森林的两个不连通节点的权值最小的边。

证明：类似上一条

次小生成树

基本定义：给一个带权的图，把图的所有生成树按权值从小到大排序，第二小的称为次小生成树。

如何求次小生成树？

方法1：先求最小生成树，再枚举删除最小生成树中的边求解。可以求出非严格次小生成树
时间复杂度：O(mlogm + nm)

方法2：先求最小生成树，再枚举不是最小生成树中的边，首先必选该边，其次选择其他边生成新的最小生成树，更新次小生成树。
时间复杂度：O(mlogm + (m - n)m)

:::info 方法1和方法2正好对偶，一个先考虑删除某条边，用剩余边求最小生成树，另一个先考虑必选某条边，用剩余边求最小生成树 :::

方法3：先求最小生成树，然后依次枚举非树边，将该边加入树中，同时从树中去掉一条边，使得最终的图仍是一棵树。且一定能求出次小生成树。
时间复杂度：O(mlogm + m + n2)
其中n2是指暴力预处理最小生成树每两个节点之间路径中边的最大值。可以用LCA代替，总时间复杂度变为O(mlogm + (m + n)logn

证明：设T为图G的一棵生成树，对于非树边a和非树边b，插入边a，删除边b的操作记为(+a, -b)。如果T + a - b后仍是一棵生成树，称(+a, -b)是T的一个可行变换。称由T进行一次可行变换所得到的新的生成树集和称为T的邻集。
定理：次小生成树一定在最小生成树的邻集中。即对于一张无向图，如果存在最小生成树和(严格)次小生成树，那么对于任何一棵最小生成树，都存在一棵(严格)次小生成树，使得这两棵树只有一条边不同。