algorithm - Kruskal 的 MST 算法是非确定性的吗？

Question

以下是来 self 们的 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。