The Algorithms Of Kruskal And Prim
Prim's algorithm: Like Kruskal's algorithm, Prim's algorithm is a special case of the generic minimumspanningtree algorithm from Growing a minimum spanning tree. Prim's algorithm operates much like Dijkstra's algorithm for finding shortest paths in a graph, which we shall see in Dijkstra's algorithm. Prim's algorithm has the property that the edges in the set A always form a single tree. As is illustrated in Figure 23.5, the tree starts from an arbitrary root vertex r and grows until the tree spans all the vertices in V. At each step, a light edge is added to the tree A that connects A to an isolated vertex of G_{A} = (V, A). This strategy is greedy since the tree is augmented at each step with an edge that contributes the minimum amount possible to the tree's weight.
Figure 23.5: The execution of Prim's algorithm on the graph from Figure 23.1. The root vertex is a. Shaded edges are in the tree being grown, and the vertices in the tree are shown in black. At each step of the algorithm, the vertices in the tree determine a cut of the graph, and a light edge crossing the cut is added to the tree. In the second step, for example, the algorithm has a choice of adding either edge (b, c) or edge (a, h) to the tree since both are light edges crossing the cut.
The key to implementing Prim's algorithm efficiently is to make it easy to select a new edge to be added to the tree formed by the edges in A. In the pseudocode below, the connected graph G and the root r of the minimum spanning tree to be grown are inputs to the algorithm. During execution of the algorithm, all vertices that are not in the tree reside in a minpriority queue Q based on a key field. For each vertex v, key[v] is the minimum weight of any edge connecting v to a vertex in the tree; by convention, key[v] = ∞ if there is no such edge. The field π[v] names the parent of v in the tree. During the algorithm, the set A from GENERICMST is kept implicitly as
A = {(v, π[v]) : v ∈ V  {r}  Q}.
When the algorithm terminates, the minpriority queue Q is empty; the minimum spanning tree A for G is thus
A = {(v, π[v]) : v ∈ V  {r}}.
MSTPRIM(G, w, r) 1 for each u ∈ V [G] 2 do key[u] ← ∞ 3 π[u] ← NIL 4 key[r] ← 0 5 Q ← V [G] 6 while Q ≠ Ø 7 do u ← EXTRACTMIN(Q) 8 for each v ∈ Adj[u] 9 do if v ∈ Q and w(u, v) < key[v] 10 then π[v] ← u 11 key[v] ← w(u, v)
Prim's algorithm works as shown in Figure 23.5. Lines 15 set the key of each vertex to ∞ (except for the root r, whose key is set to 0 so that it will be the first vertex processed), set the parent of each vertex to NIL, and initialize the minpriority queue Q to contain all the vertices. The algorithm maintains the following threepart loop invariant:
Prior to each iteration of the while loop of lines 611,

A = {(v, π[v]) : v ∈ V  {r}  Q}.

The vertices already placed into the minimum spanning tree are those in V  Q.

For all vertices v ∈ Q, if π[v] ≠ NIL, then key[v] < ∞ and key[v] is the weight of a light edge (v, π[v]) connecting v to some vertex already placed into the minimum spanning tree.
 Line 7 identifies a vertex u ∈ Q incident on a light edge crossing the cut (V Q, Q) (with the exception of the first iteration, in which u = r due to line 4). Removing u from the set Q adds it to the set V  Q of vertices in the tree, thus adding (u, π[u]) to A. The for loop of lines 811 update the key and π fields of every vertex v adjacent to u but not in the tree. The updating maintains the third part of the loop invariant.
 The performance of Prim's algorithm depends on how we implement the minpriority queue Q. If Q is implemented as a binary minheap , we can use the BUILDMINHEAP procedure to perform the initialization in lines 15 in O(V) time. The body of the while loop is executed V times, and since each EXTRACTMIN operation takes O(lg V) time, the total time for all calls to EXTRACTMIN is O(V lg V). The for loop in lines 811 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 DECREASEKEY operation on the minheap, which can be implemented in a binary minheap in O(lg V) time. Thus, the total time for Prim's algorithm is O(V lg V E lg V) = O(E lg V), which is asymptotically the same as for our implementation of Kruskal's algorithm.
 The asymptotic running time of Prim's algorithm can be improved, however, by using Fibonacci heaps shows that if V elements are organized into a Fibonacci heap, we can perform an EXTRACTMIN operation in O(lg V) amortized time and a DECREASEKEY operation (to implement line 11) in O(1) amortized time. Therefore, if we use a Fibonacci heap to implement the minpriority queue Q, the running time of Prim's algorithm improves to O(E V lg V).