Why do we need a priority queue in Prim's Algorithm

Question

As my question speaks I want to know why do we use Priority queue in Prim's Algorithm? How does it saves us from using the naive way (yes I've heard of it but don't know why).

I'd be very happy if anyone could explain step by step for adjacency list . I am using Cormen's book.

The pseudocode :

Prim(G,w,r) //what is w (weight?) and r?
  For each u in V[G]
    do key[u] ← ∞ // what is key?
       π[u] ← NIL  
  key[r] ← 0
  Q ← V[G]  
  While Q ≠ Ø
    do u ← EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

I am thinking to use std::vector then std::make_heap(); as priority queue for storing edges.

Solution 1

In prim's algorithm, there is a step where you have to get the 'nearest' vertex. This step would cost O(N) if using normal array, but it'd take only O(logN) if you use priority queue (heap for example)

Hence, the reason for using priority queue is to reduce the algorithm's time complexity (which mean it make your program run faster)

**

Update:

**

Here is Prim's algorithm's description from Wikipedia. The bold part is the part for finding nearest vertex I talked about:

Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).

Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}

Repeat until Vnew = V: Choose an edge (u, v) with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked) Add v to Vnew, and (u, v) to Enew

Output: Vnew and Enew describe a minimal spanning tree

Solution 2

You don't "need" it. In fact, a naive implementation of Prim's algorithm would simply do a linear search of the array of distances to find the next nearest vertex. Dijkstra's algorithm works the exact same way.

The reason why people use it is because it significantly speeds up the runtime of the algorithm. It turns from O(V^2 + E) to O(E*log(V)).

The key to this is the EXTRACT-MIN(Q) function. If you do it naively, this operation would take O(V) time. With a heap, it only takes O(logV) time.

Solution 3

Doing this roughly from memory, so it may be slightly inconsistent, but it gets the point across:

class Graph
  Set<node> nodes;   // The set of nodes in the graph
  MultiMap<Node, Edge> edges; // Map from Node, to a list of weighted edges connected to the node. If it weren't weighted, any spanning tree by definition would be a minimum spanning tree.

Graph Prim(Graph input):
   Graph MST = new Graph();
   PriorityQueue<Edge> candidateEdges;
   Node anyNode = input.pickAnyNodeAtRandom()
   candidateEdges.putAll(input.edges.get(anyNode));

   while MST.nodes.size() < input.nodes.size():
      edge = candidateEdges.takeLowest()  // THIS IS THE IMPORTANT PART         
      if edge.v1 in MST.nodes and edge.v2 not in MST.nodes:
         MST.nodes.add(edge.v2)       
         MST.edges.add(edge)
         candidateEdges.add(edge.v2.edges)

Basically, at each step in the algorithm, you're looking for the minimum edge with one vertex in the partial minimum spanning tree, and one vertex not in the tree, and you're going to add said edge to the tree. How do you do that efficiently? If you have a way to efficiently order all of the edges connected to a vertex in your partial spanning tree, you can simply iterate through them until you find an edge with an acceptable vertex.

Without such an ordered data structure, you'd have to iterate through all candidate edges each time to find the minimum, rather than being able to efficiently grab the minimum directly.

Solution 4

Prim's algorithm uses two Sets - lets say U and V/U.

You are starting from the root, (root is the only element in U). You place all the vertexes adjacent to it in the queue, with weight[v] = dist[root,v] where v is adjacent to root. So when you are popping from the queue, you are taking the vertex (lets say u) that has one end in U and end in V/U and is the smallest with that property. You set its weight, its parent to be root and etc... and put all its ajdacent nodes in the queue. So now the queue has all the nodes ajdacent to root and all the nodes the ajdacent to root and all the nodes ajdacent to u with their respective weights. So when you pop from it, you will once more get a node from V/U which is 'closest' to U.

In the implementation, they are initially adding every vertex to the queue with INFINITY priority, but they are gradually updating the weights, as you can see. This reflects in the priority queue as well, guaranteeng the text above.

Hope it helps.

View more solutions

Comments

[Mr.Anubis]

there is a step where you have to get the 'nearest' vertex . Can you tell what you mean by nearest vertex , are you talking about nearest adjacent vertex ? since when we take cut in graph we talk about all adjacent vertex'es to all V in A (safe edge) . Tell me i am right?

[Chan Le]

I have just add some clarification from wikipedia, hope it helps :)

[Sushant Gupta]

Very awesomely explained :) It was among one of the best explanations I found on SO. thanks mate :D

[Henley]

wait.. extract-min(Q) <- isn't this constant time since it's just pulling the first item from the priority queue?

[tskuzzy]

No, because it takes O(log V) time to restore the heap structure.

[Arpan Banerjee]

Why do we need to find the minimum? Anyways while creating the parent array we are updating if we find a minimum value later on. So, even if we had chosen a bigger value in place of the min value for the next iteration, it would be corrected later on with a min value if found