Like Kruskal's algorithm, Prim's algorithm is based on a generic MST algorithm. The main idea of Prim's algorithm is similar to that of Dijkstra's algorithm for finding shortest path in a given graph. Prim's algorithm has the property that the edges in the set A always form a single tree. We begin with some vertex v in a given graph G =(V, E), defining the initial set of vertices A. Then, in each iteration, we choose a minimum-weight edge (u, v), connecting a vertex v in the set A to the vertex u outside of set A. Then vertex u is brought in to A. This process is repeated until a spanning tree is formed. Like Kruskal's algorithm, here too, the important fact about MSTs is we always choose the smallest-weight edge joining a vertex inside set A to the one outside the set A. The implication of this fact is that it adds only edges that are safe for A; therefore when the algorithm terminates, the edges in set A form a MST.

Outline of Prim's Algorithm

Choose a node and build a tree from there selecting at every stage the shortest available edge that can extend  the tree to an additional node.

Algorithm

MST_PRIM (G, w, v)

1. Q ← V[G]
2. for each u in Q do
3.     key [u] ←  ∞
4. key [r] ←  0
5. π[r] ← NIl
6. while queue is not empty do
7.     u ← EXTRACT_MIN (Q)
8.     for each v in Adj[u] do
9.         if v is in Q and w(u, v) < key [v]
10.             then π[v] ← w(u, v)
11.                 key [v] ← w(u, v)

Analysis

The performance of Prim's algorithm depends of how we choose to implement the priority queue Q.

Definitions    Sparse graphs are those for which |E| is much less than |V|² i.e., |E| << |V|² we preferred the adjacency-list representation of the graph in this case. On the other hand, dense graphs are those for which |E| is graphs are those for which |E| is close to |V|². In this case, we like to represent graph with adjacency-matrix representation.

a. When a Q is implemented as a binary heap

We can use the BULID_HEAP procedure to perform the initialization in lines 1-4 in O(|V|) time. The while-loop in lines 6-11 is executed |V| times, and since each EXTRACT_MIN operation takes O(lg|V|) time, the total time for all calls to EXTRACT_MIN operation is O(|V| lg|V|). The for-loop in lines 8-11 is executed O(|E|) times altogether, since the sum of the lengths of all adjacency lists is 2|E|. Within the for-loop, the test for membership in Q in line 9 can be implemented in constant time by keeping a bit for each vertex that tells whether or not it is in Q, and updating the bit when the vertex is removed from Q. The assignment in line 11 involves an implicit DECREASE_KEY operation on the heap, which takes O(lg|V|) time with a binary heap. Thus, the total time for Prim's algorithm using a binary heap is O(|V| lg|V| + |E| lg |V|).

 

b. When Q is implemented as a Fibonacci heap

In this case, the performance of the DECREASE_KEY operation implicitly called in line 11 will be improved. Instead of taking O(lg|V|) time, with a Fiboncci heap of |V| elements, the DECREASE_KEY operation  will take O(1) amortized time. With a Fibonacci heap, an EXTRACT_MIN operation takes O(lg |V|) amortized time. Therefore, the total time for Prim's algorithm using a Fibonacci heap to implement the priority queue Q is O(|V| lg|V| + |E|).

 

c. When graph G = (V, E) is sparse i.e., |E| = (|V|)

From above description, it can be seen that both versions of Prim's algorithm will have the running time O(|V| lg|V|). Therefore, the Fibonacci-heap implementation will not make Prim's algorithm asymptotically faster for sparse graph.

 

d. When graph G is dense, i.e., |E| = (|V|)

From above description, we can see that Prim's algorithm with the binary heap will take |V|²lg|V| time whereas Prim's algorithm with Fibonacci-heap will take |V|². Therefore, the Fibonacci-heap implementation does not make Prim's algorithm asymptotically faster for dense graphs.

 

e. Comparing the time complexities of the two versions of Prim's algorithms, mentioned in (a) and (b), we can see that |E| is greater than |V|, the Prim's algorithm with the Fibonacci-heap implementation will be asymptotically faster than the one with the binary-heap implementation.

The time taken by Prim's algorithm is determined by the speed of the queue operations. With the queue implemented as a Fibonacci heap, it takes O(E + VlgV) time. Since the keys in the priority queue are edge weights, it might be possible to implement the queue even more efficiently when there are restrictions on the possible edge weights. If the edge weights are integers ranging from 1 to some constant w, we can speed up the algorithm by implementing the queue as an array Q[0 . . . w+1] (using the w+1 slot for key = ∞), where each slot holds a doubly linked list of vertices with that weight as their key. . Then EXTRACT_MIN takes only O(w) = O(1) time (just scan for the first nonempty slot), and DECREASE_KEY takes only O(1) time (just remove the vertex from the list its in and insert it at the front of the list indexed by the new key). This gives a total running time of O(E), which is best possible asymptotic time (since Ω(E) edges must be processed).

However, if the edge-weights are integers ranging from 1 to |V|, the array implementation does not help. The operation DECREASE_KEY would still be reduced to constant time, but operation EXTRACT_MIN would now use O(V) time, for the total running time of O(E + V²). Therefore, we are better off sticking with the Fibonacci-heap implementation, which takes O(E + VlgV) time. To get any advantage out of the integer weights, we would have to use data structure we have not studied in the CLR, such as

• The VanEmde Boas data structure mentioned in the introduction to part V: upper bound O(E + VlglgV) for prim's algorithm.
• Redistribution heap  (not in the CLR): upper bound O(E + Vsqrt{lgV}) for prim's algorithm.

Prim's Algorithm with Adjacency Matrix

Now we describe the Prim's algorithm when the graph G =(V, E) is represented as an adjacency matrix.

Instead of heap structure, we use an array to store the key of each node

1. A ← V[g] // Array
2. For each vertex uÎQ do
3.     key [u]Î ∞
4. key [r] ← 0
5. π[r] ← NIL
6. while Array A empty do
7.     scan over A find the node u with smallest key, and remove it from array A
8.     for each vertex vÎAdj[u]
9.         if vÎA and w[u, v] < key[v] then
10.             π[v] ← u
11.             key[v] ← w[u, v]

Analysis

For-loop (line 8-11) takes O(deg[u]) since line 10 and 11 take constant time. Due to scanning whole array A, line 7 takes O(V) timelines 1-5, clearly (V).

Therefore, the while-loop (lines 6-11) needs

                                                    O(∑_u(V+dg[u])) = O(V²+E)
                                                                       = O(V2)