algorithm - 将二项式堆和二叉堆的结果与 Prim 算法的 MST 进行比较。

Question

Prim 算法在 Python 2.7 中实现，可以选择优先级队列。在二项堆和二叉堆之间进行选择。数据结构是Graph(.txt文件)。如果连接了 Graph，我需要在整个 Graph 上正常运行 Prim。如果 Graph 未连接，则必须在 Graph 的 Max Connected Component 上完成 Prim 的算法。一切都设置好了，连接组件工作得很好(用小图测试)但是当二项式堆是优先级队列时，MST 结果不同于二叉堆结果(非连接图)。使用连接图时，结果是相同的。 Prim 的算法是否可能在同一个非连接图更改优先级队列上返回不同的结果？这里是 Prim 算法的“核心”。

while not pq.isEmpty():
        inode = pq.findMin()
        # here the update of the weight 
        nodes[inode] = None #Nodes marked in the MST
        pq.deleteMin()

        curr = g.adj[inode].getFirstRecord()
        while curr != None:
            #and here Decrease_Key and then a function that compare weight edges

Decrease Key in Binomial Heap是调用rebuild函数精确重建树。在二进制中，这是使用 moveUp 函数完成的。 Binomial 也在执行 findMinIndex。所以我的问题又是:Prim 的算法是否可能在同一个非连接图更改优先级队列上返回不同的结果？

Answer 1

如果您有多个相同权重的边，则生成的 MST 可能不同。 Prim 的算法不指定您选择相等边的顺序。因此，如果两个堆实现以不同方式处理相同的元素，则很可能最终会得到不同的结果。但是，如果两个解决方案中边的总长度不同，您应该开始担心了。