Prim’s Algorithm | Minimum Spanning Tree | DAA

Prim’s Algorithm

This is another algorithm for finding MST. The idea behind this algorithm is just take any arbitrary vertex and choose the edge with minimum weight incident on the chosen vertex. Add the vertex and continue the above process taking all the vertices added. Remember the cycle must be avoided.

Algorithm:

PrimMST(G)
{
T = ?; // T is a set of edges of MST
S = {s} ; //s is randomly chosen vertex and S is set of vertices
while(S != V)
{
e = (u,v) an edge of minimum weight incident to vertices in T and not forming a
simple circuit in T if added to T i.e. u ??S and v??V-S
T = T ??{(u,v)};
S = S ??{v};
}
}

Analysis:

In the above algorithm while loop execute O(V). The edge of minimum weight incident on a vertex can be found in O(E), so the total time is O(EV). We can improve the performance of the above algorithm by choosing better data structures as priority queue and normally it will be seen that the running time of prim’s algorithm is O(ElogV)!.