通用最小生成树

Question

我正在阅读有关Cormen等最小生成树的信息。以下是通用最小生成树的 。

假设我们有一个连接，无向图G =（V，E）戕重量 函数w：E-> R和我们希望找到最小生成树G. 这里我们使用贪婪方法。这种贪婪策略由 采用“通用”算法捕获，该算法一次只生成一个边缘的最小生成树 。该算法管理一组边A， ，保持以下循环不变。

在每次迭代之前，A是某个最小生成树的子集。

GENERIC-MST(G,w) 
A = NULL 
while A is not a spanning tree 
    do find an edge (u, v) that is safe for A 
    A = A ∪ {(u, v)} 
end while 

return A 

问题

1. 是什么在不变authore意味着 “A” 是最低的一些 生成树的子集？本声明中的“某些”是什么？我教过的只有一个MST。

2. 在上面的伪代码中作者所说的“A不是生成树”是什么意思？ 即，循环何时以及何时退出？

3. 在“一些”最小生成树的伪代码中，这里我的扩展名只有一个。 对不对？

任何人都可以用小例子来解释一下吗？

谢谢！

Answer 1

1.绝对不是。 MST不一定是唯一的。例如：

所有边的权重相同。

u --- v 
|  | 
|  | 
w --- x 

上面的图有4个MST，通过删除任何边缘。

2.生成树T = (V,e)在G = (V,E)是这样的：|e| = |V|-1

号

Answer 2

1. 当你说一个图的生成树是独一无二的你是正确的。但是，当图的所有边长都不相同时就​​是这种情况。正如在上面的答案中所解释的，具有相等边长的图可以有许多不同的生成树（当然，它们都具有相同的总重量）。
2. 当您在生成树中包含图形的所有顶点时，while循环就存在。为此，您在while循环中添加一个检查。

Answer 3

1. 不正确的，每@davin

2. 算法认为你有一个森林不变，但直到你补充足够的边缘森林不会跨越图。因此，你必须不断添加边，直到它们都不安全（在这一点上循环中断）。

3. 看到1

Answer 4

1. 这是错误的。即使只有两条边相等，图也可能有很多MST。

2. 一个是不是因为最小生成树：

   2.1所有首先一个不是一棵树 - 它是断开的。

   2.2它不跨越图

   当满足上面条件时

3. 它是正确的说，它是在一些 MST因为有许多的循环将退出。