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

Question

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 ?

Ivaylo Strandjev · Accepted Answer · 2015-08-27 09:08:38Z

1

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.

answered Aug 27, 2015 at 9:08

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Roberto Pavia Over a year ago

No different edges of the same weight. Weights are setted random between 0 and the number of edges. What do you mean with the length of the edges ? Didn't understand. Maybe the max number of the edges ?

Ivaylo Strandjev Over a year ago

If you select random lenghts it is possible that two have same weight

Roberto Pavia Over a year ago

Doing this with very little graph let me know which are the weights. Printing the graph they're all different. But I think it's like what you said before. Total lenght of the two solutions are different. One is an int the other one is Infinite(always). How can this even possible ? EDIT : I understand now what you mean with total length.

Ivaylo Strandjev Over a year ago

If the total length differs you have implementation error. It can not be due to using different data structures. If both are correct implementations the two solutions will have the same total length

Collectives™ on Stack Overflow

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

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related