2

我正在阅读有关 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. 在不变量中，“A”是某个最小生成树的子集，作者是什么意思？这个陈述中的“一些”是什么？我教过只有一个 MST。

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

  3. 在“一些”最小生成树的伪代码中，我的理解只有一个。我对吗？

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

谢谢！

4

4 回答 4

4

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

所有边的权重相等。

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

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

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

3.没有。

于 2011-11-16T12:22:02.970 回答
1

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

  2. A不是最小生成树，因为：

    2.1 首先，A不是一棵树——它是断开的。

    2.2 不跨越图

    满足上述条件时循环退出

  3. 说它在一些MST 中是正确的，因为它有很多。

于 2016-05-30T08:32:30.367 回答
0

  1. 根据@davin 不正确

  2. 该算法保持您拥有森林的不变量，但在您添加足够多的边之前，森林不会跨越图形。因此，您必须不断添加边，直到它们都不安全（此时循环中断）。

  3. 见 1。

于 2013-09-26T19:09:36.423 回答
0
  1. 当您说图的生成树是唯一的时，您是正确的。但是当图的所有边长都不同时就是这种情况。正如上面的答案所解释的，具有相等边长的图可以有许多不同的生成树（当然，它们都具有相同的总权重）。
  2. 当您将图形的所有顶点都包含在生成树中时，就会存在 while 循环。为此，您在 while 循环中添加一个检查。
于 2013-01-13T10:42:51.630 回答