目录
- 1 最小生成树问题
- 2 贪心选择性质
2.1 贪心选择框架——选择安全边
2.2 安全边的辨认规则 - 3 最优子结构
- 4 Kruskal算法
- 5 Prim算法
1 最小生成树问题
2 贪心选择性质
2.1 贪心选择框架——选择安全边
贪心策略：
该算法的理解：
- a.集合A总保持无环状态，因为是一棵树；因此对于集合A为安全的边(u, v)所连接的是GA中不同的连通分量；因此，每执行一次循环，减少一棵树
- b.算法执行的任意时刻，图GA = (V, A)是一个森林，GA中的每个连通分量是一棵树
算法开始时，集合A为空，森林中包含|V|棵树，每棵树只有一个节点； - c.由a, b可知，while循环总共执行|V| - 1次，当整个森林仅包含一棵树时，终止
循环不变式：
在每次循环之前，A是某棵最小生成树的一个子集。
安全边：满足如下条件的边称之为安全边。
将边(u, v)加入到集合A中，使得A不违反循环不变式，即AU{(u, v)}也是某棵最小生成树的子集。
2.2 安全边的辨认规则
切割：无向图G=(V, E)的一个切割(S, V-S)是集合V的一个划分
横跨：边(u, v)横跨切割(S, V-S)表示一个端点在集合S，一个在V-S
尊重：如果集合A中不存在横跨该切割的边，则称该切割尊重集合A
轻量级边：在横跨一个切割的所有边中，权重最小的边称为轻量级边
- 特别注意：之前将切割和尊重误解了。切割，可以将A分为不相连通的两部分，而不是将A放到一边。
贪心策略中辨认安全边的规则：
一个推论：
一个问题：为什么该切割尊重集合A
- 根据定义：因为集合A中不存在横跨该切割的边
该切割区分了C，将集合A分为两部分，C和A-C，但是C和A-C并不连通。
所以不存在横跨该切割的一条轻量级边。
3 最优子结构
如果一个问题的最优解中包含了子问题的最优解，则该问题具有最优子结构。
最小生成树是满足最优子结构的，下面会给出证明：
最优子结构描述：假设我们已经得到了一个图的最小生成树(MST) T，(u, v)是这棵树中的任意一条边。如图所示：
现在我们把这条边移除，就得到了两棵子树T1和T2，
如图：
- T1是图G1=(V1, E1)的最小生成树，G1是由T1的顶点导出的图G的子图，E1={(x, y)∈E, x, y ∈V1}
同理可得T2是图G2=(V2, E2)的最小生成树，G2是由T2的顶点导出的图G的子图，E2={(x, y)∈E, x, y ∈V2}
现在我们来证明上述结论：使用剪贴法。w(T)表示T树的权值和。
首先权值关系满足：w(T) = w(u, v)+w(T1)+w(T2)
假设存在一棵树T1'比T1更适合图G1，那么就存在T'={(u,v)}UT1'UT2'，那么T'就会比T更适合图G，这与T是最优解相矛盾。得证。 - 特别注意，上图中(u, v)这条边是连接两棵树的最小边（安全边）
4 Kruskal算法
- 集合A是一个森林，每次加入到集合A中的安全边永远是权重最小的连接两个不同分量的边。
- 运行时间分析
集合使用不相交集（并查集）实现，参见基本数据结构ADT及其实现
排序：O(ElgE)
O(E)个FIND-SET和UNION操作，|V|个MAKE=SET操作：O((V+E)α(V))
若G是连通的|E| ≥|V| -1，因此总时间为O(ElgE)，|E| < |V|²，则有O(ElgV)。
5 Prim算法——广度优先搜索
- 集合A是一棵树，每次加入到A中的安全边永远是连接A和A之外某个节点的边中权重最小的边。
- 广度优先搜索的思想——当从Q中取出一个点u时，即要检查u的所有相邻的点，并更新相关的点。
- Prim算法与分支限界法类似，利用广度优先搜索和优先队列思想，只不过是没有使用分支限界思想。因为可以证明贪心选择性质，使之可以组成一个最优解。
- 该算法的一个简要分析：
初始化：r.key = 0，其余节点u.key = 无穷大；
第一次循环：将r从Q中剔除，并更新r的所有邻节点的key
以此类推；
所有不在树A中的结点都存放在一个基于key属性的最小优先队列Q中。对于每个结点v，属性v.key保存的是连接v和树中结点的所有边中最小边的权重。 - 循环不变式：
1）A = {(v, v.π): v∈V-{r}-Q}
2）已经加入到最小生成树的结点集合为V-Q
3）对于所有的结点v∈Q，如果v.π≠NIL，则v.key < ∞并且v.key是连接结点v和最小生成树中某个结点的轻量级边(v, v.π)的权重 - 正确性：找出结点u∈Q，该结点是某条横跨切割(V-Q, Q)的轻量级边(u.π, u)的一个端点（第一次循环除外）。接着将u从队列Q中删除，并将其加入到集合V-Q中，也即将(u.π, u)加入到集合A中。
-
运行时间分析：
1）如果用二叉堆
建堆：O(V)
EXTRACT-MIN：O(VlgV)
判断结点是否属于Q：O(E)，利用一个标志位来指明结点是否属于Q（O(1)即可判断）
DECREASE-KEY：O(ElgV)
总时间为O(ElgV)
2）如果用斐波那契堆
DECREASE-KEY：O(E)
总时间为O(E+VlgV)
