PRIM’S ALGORITHM

INTRODUCTION:

Prim’s algorithm is just like Kruskal’s algorithm. It’s is also a kind of greedy algorithm. Greedy algorithm is process in which we select the best and most feasible option available at that moment. It never reverses the earlier path even if the choice is wrong.

It forms a minimum spanning tree for a weighted and undirected graph i.e., it finds subsets of edges that forms a tree including every vertex,

where the total weight of all the edges in the tree is minimized.

The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959.Therefore, it is also sometimes called the Jarník’s algorithm, Prim–Jarník algorithm, Prim–Dijkstra algorithm or the DJP algorithm.

FUNCTIONALITY AND PURPOSE:

We use prims algorithm to find minimum cost spanning tree.

If there are n vertices in weighted graph then spanning tree must have (n-1) edges.

Also, while making spanning tree keep in mind that no loop must be formed.

Now talking about the working of the formation of spanning tree, firstly start from any of the vertex then check that to which vertex it is connected and select the shortest weighted path and connect the vertex to that vertex. Follow the same process to form the spanning tree.

WORKING OF PRIM’S ALGORITHM:

Now we’ll understand this with help of an example.

So, let’s assume the graph given below.

Starting from point B it is connected to vertex A and C. Here we’ll connect B to A, since weight of A (1 unit) is less than that of C (6 unit). Similarly, we’ll then connect A to A to D, since weight of D (5 unit) is less than C (6 unit). Generally, also we cannot connect A to C because it would have formed loop which shouldn’t be formed while making spanning tree.

Now, D is connected to G and F but we’ll connect it to F. Then we’ll connect F to C. Now we cannot connect C to B because it will form loop which is not possible in formation of spanning tree.

Neither C can be connected to A, so we’ll connect C to E. Now H can be connected to E and F but we’ll connect it to F since it is smaller. No H can be connected to G and I but we will connect it to G since it is smaller than I. Now we’ll connect G to I since it is the minimum cost. So, this is the finally formed minimum spanning tree. To check we can count there are 8 edges which is vertices minus one (i.e., 9–1 = 8).

Now calculating minimum cost 1+5+2+3+7+8+7+3 = 36 units

ADVANTAGE — Prim’s algorithm helps us when we deal with dense graphs having lots of edges.

SHORTCOMINGS — Prim’s algorithm doesn’t allows control over the chosen edges when more than one edges with same weight occur.