Menu
I am studying Prim's Algorithm. There is a part within the code the next vertex across the cut will be coming to the set of the vertices belonging to the MST. While doing that, we also have to 'update all vertices in the other set which are adjacent to the departing vertex'. This is a snapshot from CLRS:
The interesting part lies in line no. 11. But since we are using a heap here, we have access to only the minimum element, right (heap[0])? So how do we search and update vertices from the heap even though they are not the minimum one and thus we have knowing where they are except by linear search?
785
Clicking on an element in one will also update the other. You can insert a key by clicking an empty tree node or array cell. Once you insert a new key, be sure to update the key to restore the min heap property as necessary. You can swap two records in the heap by first clicking one, then the other.
Prim's algorithm is similar to Dijkstra's algorithm in that they both use a priority queue to select the next vertex to add to the growing graph.
We can use heaps to implement the priority queue. It will take O(log N) time to insert and delete each element in the priority queue. Based on heap structure, priority queue also has two types max- priority queue and min - priority queue.
Using a min heap-based priority queue, the time complexity is O(ElogV). As you said, the outer while loop is O(V) because it is looping through every vertex since each one needs to be added to the MST once.
It is possible to build priority queues that support an operation called decrease-key, which takes the priority of an existing object in a priority queue and lowers it. Most versions of priority queues that ship with existing libraries don't support this operation, but it's possible to build it in several ways.
For example, given a binary heap, you can maintain an auxiliary data structure that maps from elements to their positions in the binary heap. You would then update the binary heap implementation so that whenever a swap is performed, this auxiliary data structure is updated. Then, to implement decrease-key, you could access the table, find the position of the node in the binary heap, then continue a bubble-up step.
Other pointer-based heaps like binomial heaps or Fibonacci heaps explicitly support this operation (the Fibonacci heap was specifically designed for it). You usually have an auxiliary map from objects to the node they occupy in the heap and can then rewire the pointers to move the node around in the heap.
Hope this helps!
174
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
