是的,这是家庭作业。我想知道是否有人可以解释Sollin(或Borůvka)算法确定最小生成树的过程。此外,如果您能解释如何确定最坏情况下的迭代次数,那就太好了。
4781 次
2 回答
6
在顶层,该算法的工作原理如下:
- 保持一些子图有许多生成树。最初,图的每个顶点都是一个没有边的 mst。
- 在每次迭代中,对于每个生成树,找到将其连接到另一棵生成树的最便宜的边。(这是一个简化。)
就迭代而言,最坏的情况是您总是合并成对的树。在这种情况下,您拥有的树的数量将在每次迭代中减半,因此迭代次数与节点数成对数。
还要注意,在选择要添加的边时有一个特殊的技巧:如果你不小心,当树 A 连接到树 B、树 B 连接到树 C、树 C 连接到树 A 时,你可能会引入一个圆。(这只有在选择的所有三个边具有相同的权重时才会发生。诀窍是有一个任意但固定的平局,就像边的固定顺序一样。)
这就是我的索引卡背面概述。
于 2010-11-19T20:57:20.140 回答
0
我使用的是外行的术语。
- 首先选择一个顶点
- 检查该顶点的所有边并选择一个具有最小权重的边
- 对所有顶点执行此操作(可能会多次选择某些边)
- 您将获得连接的组件。
- 从这些连接的组件中选择一个权重最小的边。
将形成具有最小权重的生成树
于 2013-01-23T14:30:29.507 回答