最小生成树
目录
最小生成树：Kruskal算法和Prim算法的实现
这里直接给出离散数学中的几个定理和推论：
- 无向图G具有生成树当且仅当G连通.
- G为n阶m条边的无向连通图，则 m >= n - 1.
- G是树 $\Leftrightarrow$ G中任意两个顶点之间存在唯一路径 $\Leftrightarrow$ G中无回路且m=n-1$\Leftrightarrow$ G是连通的且m=n-1$\Leftrightarrow$ G中没有回路但在任何2个不同的顶点间加一条新边就能在图中得到唯一的含新边的环圈.
- 生成子图指的是顶点集相同，但边集是图G的子集的图.
- 生成树指的是图G的生成子图并且是树.
- 最小生成树指的是图G的所有生成树中权最小的.
算法第4版中这样定义：
- 树是一幅无环连通图。
- 连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。
- 加权图是一种为每条边关联一个权值或是成本的图模型。
- 一幅加权图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树。
- 图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点的边。
- （切分定理）。在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。切分定理是解决最小生成树问题的所有算法的基础。
看了一下算法第4版，真的很有帮助，特别是它的几个API的定义，很像ACM模式的输入，对笔试有一定的帮助。
图的表示
邻接矩阵？需要$n^2$的空间，而有百万个顶点的图是很常见的……
邻接表？可以！用一个顶点为键，值为顶点数组，其中的每个元素都是与该顶点相邻的顶点。
此后记住了，咱一般就是用邻接表。
加权无向图的表示
在邻接表的表示中，可以在链表的结点中增加一个权重域。
Prim 算法：横切边
- 初始时只有一个顶点。
- 每一步都为生长中的树添加一条边，总共添加 $V-1$条。
- 每次都是加入一条这样的边（横切边）：连接树中顶点与不在树中顶点并且权重最小的边。
实现思路：
算法第四版给出了两种实现，一种Lazy的，一种即时的。
我们需要一个顶点集合的布尔数组表示某顶点是否在MST中，一个队列来保存MST中的边，还需要用优先队列来根据权重比较横切边。
如何维护横切边的集合呢？每向树中添加一条边也就添加了一个顶点，那么横切边集合将有失效的。此外，我们感兴趣的只是连接树顶点与非树顶点中权重最小的边，因此只需要保存权重最小的那条边，当有顶点进入树的时候，看顶点的引入是否使得权重更小了。
伪代码：
(1) 将顶点0（起点）加入最小生成树，并遍历与起点相连的所有边，将权重最小的放入优先队列pq
(2) while (mstNodeCnt < n) {
从优先队列pq中取出权重最小的边，将该边加入MST；
同时将改变对应的顶点V加入MST，并遍历与V相连的所有横切边，找到权重最小的加入优先队列pq;
mstNodeCnt++;
}
Kruskal 算法：连接一片森林中的两棵树
- 初始时选择最小权重的一条边。
- 每一步都为生长中的树添加一条边，总共添加 $V-1$条。
- 每次都是加入一条这样的边：权重最小并且不会和已经加入的边构成环。
实现思路：
我们将会使用一条优先队列来将边按照权重排序，用一个并查集来识别会形成环的边，以及一条队列来保存最小生成树的所有边。
相比Prim算法，我认为 Kruskal 算法实现起来更简单。
伪代码：
（1）对所有的边从小到大排序
（2）while(mstEdgeCnt < n - 1) do{
取权值最小的边（u，v）；
if（u，v不连通）{
将（u，v）加入T；
mstEdgeCnt++;
}
将边（u，v）从集合E中删除；
}