algorithm - Sollin 的最小生成树算法

Question

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

Answer 1

在顶层，该算法的工作原理如下：

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

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

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

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

Answer 2

我使用的是外行的术语。

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

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