Bre*_*dan -1 algorithm discrete-mathematics
是的,这是功课.我想知道是否有人可以解释Sollin(或Borůvka)算法确定最小生成树的过程.此外,如果你能解释如何在最坏的情况下确定迭代次数,那就太好了.
在顶层,算法的工作原理如下:
迭代方面最糟糕的情况是你总是合并树的对.在这种情况下,您拥有的树的数量将在每次迭代中减半,因此迭代次数在节点数中是对数的.
另请注意,选择要添加的边有一个特殊的技巧:如果不小心,当树A连接到树B时,可能会引入一个圆,树B连接到树C,树C连接到树A.只有当所有选择的三条边都具有相同的权重时才会发生这种情况.诀窍是有一个任意但固定的断路器,就像边缘的固定顺序一样.)
那么,那是我的索引卡概述.