-1

是的,这是家庭作业。我想知道是否有人可以解释Sollin(或Borůvka)算法确定最小生成树的过程。此外,如果您能解释如何确定最坏情况下的迭代次数,那就太好了。

4

2 回答 2

6

在顶层,该算法的工作原理如下:

  • 保持一些子图有许多生成树。最初,图的每个顶点都是一个没有边的 mst。
  • 在每次迭代中,对于每个生成树,找到将其连接到另一棵生成树的最便宜的边。(这是一个简化。)

就迭代而言,最坏的情况是您总是合并成对的树。在这种情况下,您拥有的树的数量将在每次迭代中减半,因此迭代次数与节点数成对数。

还要注意,在选择要添加的边时有一个特殊的技巧:如果你不小心,当树 A 连接到树 B、树 B 连接到树 C、树 C 连接到树 A 时,你可能会引入一个圆。(这只有在选择的所有三个边具有相同的权重时才会发生。诀窍是有一个任意但固定的平局,就像边的固定顺序一样。)

这就是我的索引卡背面概述。

于 2010-11-19T20:57:20.140 回答
0

我使用的是外行的术语。

  • 首先选择一个顶点
  • 检查该顶点的所有边并选择一个具有最小权重的边
  • 对所有顶点执行此操作(可能会多次选择某些边)
  • 您将获得连接的组件。
  • 从这些连接的组件中选择一个权重最小的边。

将形成具有最小权重的生成树

于 2013-01-23T14:30:29.507 回答