Priority queue and Prim's Algorithm

Question

I have gone through the C++ reference manual and am still unclear on how to use the priorityqueue data structure in STL.

So, basically I have been trying to implement my own using heaps.

I am doing this for implementing Prim's algorithm.

Vector <int, int> pq;

This is my priority queue. The first field is the node and the second field the weight to the existing tree.

I plan to modify the values of weight in pq every time a new node is added to the tree by updating the weights of its neighbour nodes.

• How do I access the individual elements of this vector? I also need to be able to delete elements at will.

Is this a good way to implement a priority queue? what if I want to add another field to the container, namely

Vector<int, int, int> MST

• How would I access the third element? I want to store the resulting MST this way such that the first two fields represent the vertices forming the edge, and the third the weight.

It would also help if someone could tell me how to assign elements to this vector using push_back.

• Also, would the conventional C++ STL priority queue help in this as I need to update the priority values each time a new element is added to the MST? Would it self-correct itself according to the priority when values are modified?

• One other question, these Vectors, when I pass them to a function, and try to make changes, is it a pass by value or pass by reference - Or, are the changes reflected outside the function?

Answer 1

In Prim's algorithm the random access to elements not needed. You just need to skip elements from the queue which connect already connected and pass forward.

So the algorithm looks as follows:

1. choose a node N
2. add all edges from N to the PQ
3. pop a minimal cost edge from PQ
   • if it connects nodes which are already in the tree, skip it
   • otherwise add this edge to the tree, call the new node N and go back to point 2.

After adding the node just check if size of the tree is already size of graph - 1. If so then finish.

Note that the only operations on PQ are add_element and pop_minimum - thus std::priority_queue will work.