1

以下是我们 CS 算法讲师的 Kruskal 最小生成树算法的伪代码。我想知道 MST 算法是否是不确定的。给定具有相同权重的两条边，如果在添加到 T 时没有一条边形成循环，算法将如何在它们之间做出决定。当然，如果它是随机的，那么我们无法确定将哪些确切边添加到 T 的结果？

    Given an undirected connected graph G=(V,E)    
    T=Ø //Empty set, i.e. empty
    E'=E
    while E'≠Ø do
    begin
        pick an edge e in E' with minumum weight
        if adding e to T does not form a cycle then
            T = T∪{e} //Set union, add e to T
        E' = E'\{e} //Set difference, remove e from E'
    end

谢谢！

4

2 回答 2

3

如果您为有选择的情况选择确定性选择函数，则克鲁斯卡尔算法是确定性的，否则它是非确定性的。如果您随机选择，如果有多种可能性，您无法判断哪些边最终会出现在 MST 中。

于 2012-05-26T15:28:31.360 回答
2

给定具有相同权重的两条边，如果在添加到 T 时没有一条边形成循环，算法将如何在它们之间做出决定。当然，如果它是随机的，那么我们无法确定将哪些确切边添加到 T 的结果？

这取决于实施。

Kruskal 的算法找到连接加权图（不是树）的许多可能的 MST 之一。这是因为在每次迭代中，您都有多种选择（从具有相同权重的边中选择边）。这是非确定性位。当然，当您实现算法时，您将做出选择（即强加一个顺序），但是不同的实现可以很好地强加一个不同的顺序。因此，您将拥有算法的两个实现，正确地解决相同的问题，但最终结果可能不同。

于 2012-05-26T15:29:30.867 回答