CODEWITHSUNDEEP
algorithmpython-2.7graphpriority-queueminimum-spanning-tree
Roberto Pavia
Roberto Pavia

Reputation: 75

Comparing the result of Binomial Heap and Binary Heap with Prim's Algorithm for MST.

Prim's Algorithm implemented with the possibility to choose priority queue in Python 2.7. The choice is between Binomial Heap and Binary Heap. Data structure are Graph (.txt file). If Graph is connected I need to run normally Prim on the whole Graph. If Graph is not connected , Prim's algorithm have to be done on the Max Connected Component of the Graph. Everything is well setted , connected component work great (tested with little graph) but when Binomial Heap is the priority queue , MST result is different from Binary Heap result (non connected Graph). When using connected graph the results are the same. Is possible that Prim's Algorithm return different results on the same non-connected graph changing priority queue ? Here the 'heart' of Prim's Algorithm. 

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 is calling the rebuild function to precisely rebuild the tree. In Binary this is done using the moveUp function. Also Binomial is doing the findMinIndex. So again my question is : Is possible that Prim's Algorithm return different results on the same non-connected graph changing priority queue ?

Upvotes: 0

Views: 459

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

It is possible that the resulting MST differ if you have multiple edges of the same weight. Prim's algorithm does not specify the order in which you select equal edges. Thus if the two heap implementation handle equal elements differently it is quite possible that you end up with different result. However if the total length of the edges in the two solutions differs you should start worrying.

Upvotes: 1

Related Questions