用Prim算法比较二项式堆和二进制堆的MST结果。

Question

Prim的算法在Python 2.7中实现了选择优先级队列的可能性。在二项式堆和二进制堆之间进行选择。数据结构是图形（.txt文件）。如果图是连通的，我需要在整个图上正常运行Prim。如果图不连通，则必须对图的最大连通分量执行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

二项式堆中的减少键是调用重建函数来精确重建树。在二进制中，这是使用moveUp函数完成的。二项式也在进行findMinIndex。因此，我的问题是：Prim的算法是否可能在相同的非连通图改变优先级队列上返回不同的结果？

Answer 1

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