最小生成树

MST

定义：一个无向图中的一棵生成树，满足其边权和最小。对于一个无向图，其不一定唯一。

同时满足另外两个性质：

1. 在一棵生成树 \(T\) 中，任意两个点 \(i,j\) 的路径上最大边权记为 \(\operatorname{bottleneck}_{T, {i,j}}\)（瓶颈）。那么对于图上任意一棵最小生成树 \(MST\) 和任意的 \(i,j\) 和任意的 \(T\) 都有 \(\operatorname{bottleneck}_{MST, {i,j}} \le\operatorname{bottleneck}_{T, {i,j}}\)。
2. 考虑整个生成树的最大边权，MST 的也是所有生成树中最小。

Kruskal

时间复杂度 \(O(m \log m)\)。（排序）
证明：Kruskal 算法在任意时刻找到的生成森林一定是一个 MST 的一部分。这里考虑 MST 的定义证明。

考虑归纳。对步骤归纳。显然第 \(0\) 步骤满足题意。

考虑某一个步骤选择的生成森林为 \(F\)，其对应的生成树是 \(T\)。在下一步中加边 \(e\)。证明 \(F+e\) 是某一个 MST 的一部分。

• 如果 \(F+e \in T\)，那么显然成立。
• 否则，考虑 \(T+e\) 是一个基环树。找到其中的一个环。找到其中一个还没有加入的边 \(e'\)。显然 \(e \le e'\)。如果 \(e <e'\)，那么 \(T - e' + e\) 是一棵小于 \(T\) 的树，\(T\) 不是 MST；否则，\(T - e' +e\) 是一棵等于 \(T\) 的树，也是 MST。

主要思想是，将需要讨论的很复杂的一棵树换成一个环来讨论。

Prim

加点。
考虑已经加入 MST 的点集 \(S\) 和还没有加入 MST 的点集 \(T\)。维护的 \(S\) 一直是一棵生成树（而不是森林），每次加一个点和一条边。
定义一个点的距离 \(dis_i\) 表示 \(i\) 距离 \(S\) 的距离（或者形式化地说，距离 \(S\) 中每一个点的距离的最小值）。每次加入 \(dis\) 最小的一个点。并且更新其他点的 \(dis\)。

时间复杂度：
类似 dijkstra，是 \(O((n+m) \log (n + m))\) 的。主要是因为二叉堆不支持高效率的 decrease key （修改某个权值）操作。pbds 有配对堆/Fib 堆，不太了解，可以满足这个性质，理论上是 \(O(n \log n + m)\) 的。

证明：
依然是讨论一个环来简化思考。

考虑之前一定选了这个环的一个半包。

这次只可能选临近的两条边。

考虑某一条边如果没有选，另一条边一定有选。那么就很好证明了。