12

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:

enter image description here

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?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
SexyBeast
  • 7,913
  • 28
  • 108
  • 196

2 Answers2

9

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Yeah, in fact hash is the first thing that came to my mind, but no tutorial bothered to mention it, so I thought that they are doing it without using one.. – SexyBeast Jun 12 '13 at 23:01
  • So, in that case, it will be something like this: Find all adjacent nodes to the node in question, for each, find its position in the heap from the hash. Then decrease and bubble up each entry, and update the corresponding value in the hash with the new position. Right? – SexyBeast Jun 12 '13 at 23:02
  • @AttitudeMonger- That's mostly it - just remember that you have to update the positions of all the swapped nodes as well! – templatetypedef Jun 12 '13 at 23:07
  • I didn't get that, please explain a bit more! – SexyBeast Jun 12 '13 at 23:07
  • 1
    @AttitudeMonger- The positions of all of the elements in the heap has to be consistent with what the hash table says, so any time you perform a swap in the heap, you have to update the positions in the hash table as well. Does that make sense? – templatetypedef Jun 12 '13 at 23:11
  • Oh okay okay, so apart from updating the position of the to-be-updated node in the hash at the end of the bubble, I will have to constantly update the positions of the nodes I am swapping during the bubbling as well, right? – SexyBeast Jun 12 '13 at 23:13
  • Yeah of course..But one thing, imagine I have two adjacent nodes to update, while bubbling to update the first one, it comes to the 2nd one also, which I update. After this bubbling is completed, should I now update the 2nd one also, given that it was already once updated during the bubbling of the first vertex? – SexyBeast Jun 12 '13 at 23:27
  • @AttitudeMonger- Yes. The updates are independent. (Try drawing some pictures... I think you'll see what's going on here.) – templatetypedef Jun 12 '13 at 23:30
2

Pointers enable efficient composite data structures

You have something like this (using pseudocode C++):

class Node
    bool visited
    double key
    Node* pi
    vector<pair<Node*, double>> adjacent //adjacent nodes and edge weights
    //and extra fields needed for PriorityQueue data structure
    // - a clean way to do this is to use CRTP for defining the base
    //   PriorityQueue node class, then inherit your graph node from that

class Graph
    vector<Node*> vertices

CRTP: http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

The priority queue Q in the algorithm contains items of type Node*, where ExtractMin gets you the Node* with minimum key.

The reason you don't have to do any linear search is because, when you get u = ExtractMin(Q), you have a Node*. So u->adjacent gets you both the v's in G.Adj[u] and the w(u,v)'s in const time per adjacent node. Since you have a pointer v to the priority queue node (which is v), you can update it's position in the priority queue in logarithmic time per adjacent node (with most implementations of a priority queue).

To name some specific data structures, the DecreaseKey(Q, v) function used below has logarithmic complexity for Fibonnaci heaps and pairing heaps (amortized).

More-concrete pseudocode for the algorithm

MstPrim(Graph* G)
    for each u in G->vertices
        u->visited = false
        u->key = infinity
        u->pi = NULL
    Q = PriorityQueue(G->vertices)
    while Q not empty
        u = ExtractMin(Q)
        u->visited = true
        for each (v, w) in u->adjacent
            if not v->visited and w < v->key
                v->pi = u
                v->key = w
                DecreasedKey(Q, v) //O(log n)
Timothy Shields
  • 75,459
  • 18
  • 120
  • 173