克鲁斯卡尔的MST算法是不确定的？

Question

以下是我们的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

谢谢！

Answer 1

如果你

为有选择的情况选择一个确定性选择函数，Kruskal的算法是确定性的，否则它是非确定性的。如果随机选择，则无法判断哪些边最终出现在 MST 中（如果存在多种可能性）。

Answer 2

给定两条具有相同权重的边，算法将如何决定 如果两条边在添加到 T 时都没有形成循环，则它们之间。 如果它是随机的，那么就无法确定确切的结果 边缘被添加到T？

这取决于实施。

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