Prim’s algorithm

Kruskal’s algorithm and Prim’s algorithm. Each can easily be made to run in time O(E log V ) using ordinary binary heaps. By using Fibonacci heaps, Prim’s algorithm can be sped up to run in time O(E + V log V ), which is an improvement if |V | is much smaller than |E|. The two algorithms are greedy algorithms. At each step of an algorithm, one of several possible choices must be made. The greedy strategy advocates making the choice that is the best at the moment. Such a strategy is not generally guaranteed to find globally optimal solutions to problems.

Like Kruskal’s algorithm , Prim’s algorithm is a unique instance of the conventional minimum spanning tree algorithm. Prim’s algorithm works similar as Dijkstra’s algorithm for finding briefest ways in a graph. Prim’s Algorithm has the property that the edges in the set A consistently structure a solitary tree. As is represented in Figure1, the tree begins from a self-assertive root vertex r and develops until the tree traverses all the vertices in V . At each progression, a light-weight edge is added to the tree A that associates A to a disconnected vertex of G A = (V, A). This standard adds just edges that are alright for A; along these lines, when the algorithm ends, the edges in A structure a base traversing tree. This methodology is avaricious since the tree is expanded at each progression with an edge that contributes the base sum conceivable to the tree’s weight. The way to executing Prim’s Algorithm productively is to make it simple to choose another edge to be added to the tree framed by the edges in A. In the pseudocode beneath, the associated chart G and the root r of the base crossing tree to be developed are contributions to the algorithm.

Figure 1 The root vertex is shaded edges are in the tree are 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.

During execution of the algorithm, all vertices that are not in the tree live in a min-priority Queue Q dependent on a key field. For every vertex v, key[v] is the base load of any edge associating v to a vertex in the tree; by show, key[v] = ∞ if there is no such edge. The field π [v] names the parent of v inside the tree. During the algorithm, the set A from GENERIC-MST is kept verifiably as

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

At the point when the algorithm ends, the min-priority queue Q is unfilled; the minimum spanning tree A for G is hence

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

MST-PRIM (G, w, r)

Prim’s Algorithm fills in as demonstrated in Figure 1. Lines 1–5 set the key of every vertex to ∞ (with the exception of the root r, whose key is set to 0 so it will be the primary vertex prepared), set the parent of every vertex to NIL, and introduce the min-priority Queue Q to contain all the vertices. The algorithm keeps up the accompanying three-section loop invariant:

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

1. A = {(v, π [v]) : v ∈ V − {r} − Q}
2. The vertices already placed into the minimum spanning tree are those in V−Q.
3. 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) (except for 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 updates 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 initialisation 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(log V) time, the total time for all calls to EXTRACT-MIN is O(V log 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(log V ) time. Thus, the total time for Prim’s algorithm is O(V log V + E log V ) = O(E log 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. If |V| elements are organised into a Fibonacci heap, we can perform an EXTRACT-MIN operation in O(log 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 log V ).