23. 最小生成树

引：在设计电子电路时，我们常常需要将多个组件的针脚连起。若要连接n个针脚，可以用n-1根连线，我们希望使用的最短的连线来连接针脚。

最小生成树问题：
一个连通无向图$G = (V, E)$中，对于每条边$(u, v) \in E$，为其赋予权重$w(u, v)$。找到一个无环子集$T \subseteq E$，使得所有的结点可以互相到达，并且具有最小的权重，即：$w(T) = \sum_{(u, v) \in T}w(u, v)$的值最小。$T$就是图$G$的最小生成树。

下图中阴影部分组成的就是最小生成树。

生成最小生成树

本章将介绍两种生成最小生成树的算法，他们都用了贪心策略。

思想：创建一个边的集合A，首先讲集合A设置为空集，每次循环加入一条安全的边到集合A中，是的A是最小生成树T的子集，直到集合A覆盖了所有结点。

下面是这个贪心策略的伪代码：

如何找出一个安全的边

这个贪心策略的重点就是如何找出安全的边。

设边集合A覆盖的结点集合为S，没覆盖到的结点集合为V-S。想要生成最小生成树，则必须有且仅有一条边连接S和V-S（连接两个集合的意思为边的一头在S中，另一头在V-S中），所有连接S和V-S的边中权重最小的边就是安全的边。

可以用反证法证明这种选择安全的边的方法是正确的。

Kruskal算法

思想：初始时，将$|V|$个结点视为$|V|$棵树并组成森林。所有边的权重按照从小到大排序，从最小的边开始编译，如果这个边能连接森林中的两棵树，则将这条边加入集合A，并且将这两棵树合并为一棵树。直到森林中只剩一棵树。

伪代码和事例如下：

Prim算法

思想：初始时，给所有的结点赋予一个无穷大的key值，并加入优先队列。每次循环时，从优先队列中取出一个key值最小的结点u加入集合A中，并且更新优先队列中所有与结点u相连的结点v的key值（如果$w(u,v) < v.key$，则$v.key = w(u,v)$）。直到优先队列为空。

伪代码和事例如下：

TODO:时间复杂度分析