1. 定义和约定

1.1 定义

  • 给定一个无向加权图
  • 生成树指找出一个含有所有节点的无环连通子图

  • 最小生成树指保证生成树中所有边的权值之和最小

    1.2 约定

  • 只考虑联通图，如果一个图是非连通的，那么只能计算所有连通分量的最小生成树

  • 边的权重可能会为0或者负数，如果边都是正的，那么直接将最小生成树定义为连接所有顶点且总权重最小的子图就行

  • 所有边的权重各不相同，不然可能会让最小生成树不唯一

    2. 原理

    2.1 树的基本性质

  • 用一条边连接树中任意两个顶点会产生一个新的环

  • 从树中删去一条边将会得到两棵独立的树

    2.2 切分定理

  • 切分：将图的所有顶点分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点的边

    • 就是说切分把顶点分成两部分，两部分的点之间可能会有边存在，这些边就是横切边
  • 切分定理：在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树
    • 就是说两部分的点之间存在的边中，最小的那个边一定是在生成树中的
  • 证明：
    • e为权重最小的横切边，T为图中的最小生成树
    • 假设T不包含e，那么如果将e加入T，得到的图必然会有一条经过e的环
    • 这个环至少含有含有另一条横切边，设为f，f的权重必然大于e
    • 那么我们删掉 f 而保留 e 就可以得到一棵权重更小的树，和假设矛盾

  • 自己的想法：

    • 这个遗留下最小的横切边的设定，代表了在某次或多次建立树的过程中，没有选择这条横切边而导致后面产生了连锁反应，于是最终这个选取最小的横切边的设定被抛弃了
    • 在这个背景下把横切边加上，从而打脸了之前的设定。于是每个子过程中，一旦出现了最小的横切线如果没有选中的情况，那就违反了原则；原则是从根本上进行打脸的，而不是细节过程
    • 再考虑一个极端点的细节：我只是在某次确定横切边时，没有选中最小的边。那么将这个边放上去形成环，再删除一个边时，结果还真不一定是像证明所愿，这里就是一个重要的逻辑：e是权重最小的横切边。所以定理中的这个e应该是小于环中的其他边的
    • 如果我将局部获得的横切边排除（割裂）掉，那么定理适用于未生成子树的另一半。那么剩下的就是在二者之间获取那个最小的横切边来连通起来。这样又符合了我们定理的情形。（卧槽这不就是递归吗，我觉得这个想法可）

      2.3 贪心算法

  • 实际上，解决最小生成树问题的算法，都是一种贪心算法的特殊情况

    • 利用切分定理找到最小生成树的一条边，不断重复直到找到所有的边
    • 不同算法的区别在于：保存切分和判定权重最小的横切边的方式

2.4 Prim算法

  • 一开始只有一个顶点，然后每一步都为树添加一条边，共添加V-1条边
  • 每次连接的边，是树中的顶点与不在树中的顶点之间相连且权重最小的边
  • 证明：就是正常的切分定理
  • ElogE

2.5 Kruskal算法

  • 按边的权重顺序（从小到大）处理他们，将边加入最小生成树当中
  • 加入边的过程中保证不和已经加入的边构成环，直到树中含有V-1条边为止
  • 证明：反正是能够连续选择到权重最小的横切边，和贪心的目的一致
  • ElogE