Question

最小生成树

Answer 1

参见贪心算法——最小生成树算法

贪心策略：

该算法的理解：

循环不变式：键亩
在每次循环之前，A是某棵最小生成树的一个子集。

安全边：满足如下条件的边称之为安全边。
将边(u, v)加入到集合A中，使得A不违反循环不变式，即AU{(u, v)}也是某棵最小生成树的子集。

贪心策略中辨认安全边的规则：

一个推论：

如果一个问题的最优解中包含了子问盯亮绝题的最优解，则该问题具有最优子结构。
最小生成树是满足最优子结构的，下面会给出证明：
最优子结构描述：假设我们已经得到了一个图凯姿的最小生成树(MST) T，(u, v)是这棵树中的任意一条边。如图所示：

现在我们把这条边移除，就得到了两棵子树T 1 和T 2，
如图：