通用最小生成树
我正在阅读有关科门的最小生成树等内容。以下是 通用最小生成树。
假设我们有一个连通的无向图 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
问题
作者在不变量中意味着什么“A”是某个最小值的子集 生成树？这句话中的“一些”是什么？我教过只有一个 MST。
在上面的伪代码中，作者所说的“A不是生成树”是什么意思？ 即， while 循环如何以及何时退出？
在伪代码中，“一些”最小生成树，这里我的理解只有一个。 我对吗？
任何人都可以用小例子解释一下吗？
谢谢！
I am reading myself about Minimum Spanning trees in Cormen,etc. Following is the
generic minimum spanning tree.
Assume we have a connected, undirected graph G = (V, E) witha a weight
function w:E->R and we wish to find a minimum spanning tree for G.
Here we use greedy approach. This greedy strategy is captured by the
following "generic" algorithm, which grows the minimum spanning tree
one edge at a time. The algorithm manages a set of edges A,
maintaining the following loop invariant.Prior to each iteration, A is subset of some minimum spanning tree.
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
Questions
What does authore mean in invariant that "A" is subset of some minimum
spanning tree? What is "some" in this statement? i taught there is only one MST.In above pseudocode what does author mean by "A is not a spanning tree"?
i.e., how and when while loop exits?In pseudo code where "some" minimum spanning tree, here my understading is only one.
am i right?
Can any one pls explain with small example?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
1.绝对不是。 MST 不一定是唯一的。例如：
所有边的权重相等。
上图通过删除任何边有 4 个 MST。
2.
G = (V,E)中的生成树T = (V,e)满足|e| = |V|-13. 否。
1. Absolutely not. MST are not necessarily unique. For example:
All edges are of equal weight.
The above graph has 4 MSTs, by removing any edge.
2. A spanning tree
T = (V,e)inG = (V,E)is such that|e| = |V|-13. No.
这是错误的。即使只有两条边相等，图也可能有许多 MST。
A 不是最小生成树，因为：
2.1 首先，A 不是一棵树 - 它是断开连接的。
2.2 不跨越图表
满足上述条件时循环将退出
说它在 some MST 中是正确的，因为有很多。
This is false. A graph may have many MST even if only two edges are equal.
A is not minimum spanning tree because of:
2.1 First of all A is not a tree - it is disconnected.
2.2 It does not span the graph
The loop will exit when the above conditions are met
It is correct to say that it is in some MST as there are many.
根据@davin 不正确
该算法维护您拥有森林的不变量，但在您添加足够的边之前，森林不会跨越图形。因此，您必须不断添加边，直到没有一条边是安全的（此时循环中断）。
参见 1。
Incorrect as per @davin
The algorithm maintains the invariant that you have a forest, but the forest will not span the graph until you add enough edges. Thus you have to keep adding edges until none of them are safe (at which point the loop breaks).
see 1.