Sollin的最小生成树算法

-1

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

2010-11-19 Brendan

http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm？如果有什么具体的东西你不明白，就问一下。否则，请阅读您的教科书，维基百科，维基百科的来源等。 – nmichaels 2010-11-19 20:54:16

有人能解释为什么这个Gareth Rees人不断从这个问题中删除标签“离散数学”，为什么它被拒绝投票？我没有生气;我只是不太了解这个网站的工作方式，因为我是新手。这个问题在这类网站上似乎是一个合理的问题，我相信它属于离散数学，尤其是因为这个作业来自一门名为“离散数学”的课程。 – Brendan 2010-11-19 21:13:04

离散数学是与整数（而不是连续数学）相关的主题集合。所以，序列，递归，求和，生成函数，二项式，有限微积分等等。算法为离散数学提供了很多*例子，但这并不意味着所有关于算法的问题都是关于离散数学的问题。至于downvotes，我不知道。（我认为你的问题很好，只是误标。） – 2010-11-19 23:17:21

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

保持你有一个跨越数为一些子图树。最初，图的每个顶点都是m.s.t.没有边缘。
在每次迭代中，对于您的每个生成树，找到将其连接到另一棵生成树的最便宜的边。（这是一个简化。）

在迭代方面最糟糕的情况是，你总是合并树对。在这种情况下，每次迭代中树的数量会减半，所以迭代的次数是节点数的对数。

另请注意，在选择要添加的边时有一个特殊技巧：如果您不小心，可能会在树A连接到树B时引入一个圆，树B连接到树C并且树C连接到树A（只有当所选的三条边都具有相同的权重时，才会发生这种情况）诀窍是要有一个任意但固定的分频器，就像固定的边缘顺序一样。）

所以那里，那是我的背部索引卡概述。

来源

2010-11-19 20:57:20

那么在100节点树的情况下，最糟糕的情况会需要log2（100）或7次迭代？ – Brendan 2010-11-19 21:09:24

@布伦丹：是的，听起来没错。我承认我并不关心O（） - Notation隐藏在你身上的常量因素，但我不认为这里有任何内容。 – 2010-11-19 21:11:23

谢谢。我想你的解释和我的研究之间，我正确使用这个算法。 – Brendan 2010-11-19 21:18:33

我使用外行的术语。

首先选择一个顶点
检查从顶点所有的边缘，并选择具有最小重量
这样做对所有的顶点（一些边缘可以选择多个一次）
您将获得连接的组件。
从这些连接的组件中选择一个重量最轻的边。

您以最小的重量生成树将形成

来源

2013-01-23 14:30:29

Sollin的最小生成树算法

回答

相关问题