The Algorithms Of Kruskal And Prim

Prim's algorithm: Like Kruskal's algorithm, Prim's algorithm is a special case of the generic minimum-spanning-tree 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 min-priority 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 GENERIC-MST is kept implicitly as

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

When the algorithm terminates, the min-priority queue Q is empty; the minimum spanning tree A for G is thus

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

	MST-PRIM(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 ← EXTRACT-MIN(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 1-5 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 min-priority queue Q to contain all the vertices. The algorithm maintains the following three-part loop invariant:

Prior to each iteration of the while loop of lines 6-11,

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 8-11 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 min-priority queue Q. If Q is implemented as a binary min-heap , we can use the BUILD-MIN-HEAP procedure to perform the initialization in lines 1-5 in O(V) time. The body of the while loop is executed |V| times, and since each EXTRACT-MIN operation takes O(lg V) time, the total time for all calls to EXTRACT-MIN 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 min-heap, which can be implemented in a binary min-heap 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 EXTRACT-MIN operation in O(lg V) amortized time and a DECREASE-KEY operation (to implement line 11) in O(1) amortized time. Therefore, if we use a Fibonacci heap to implement the min-priority queue Q, the running time of Prim's algorithm improves to O(E V lg V).

SKEDSOFT