Prim’s Minimum Spanning Tree

Prim’s Algorithm is a greedy algorithm which works on the approach of going for the best available option out of all. This algorithm uses min heap to store the weights of the vertices and edges of the tree. Here, we first create a min heap having the size of its number of vertices(V), Accordingly, the Number of edges of the tree are vertices minus 1(V-1).

The Spanning tree being the subset of a graph G(Vertices, Edges), spans every vertex of the graph and contains all the vertices present in the original graph.

Prim’s algorithm will work on picking the minimum key value which is not already present in the MST and make it’s path through it. The rule applies that the tree should not be connected from all vertices i.e. it shouldn’t form a circular tree.

It is more like starting with an arbitrary node from vertex V and here you can’t form a forest instead growing a MST where the ideology is that you have to maintain MST for V’ being a subset of V.

What is the Procedure??

Basic Procedure behind the working of Prim’s Algorithm is first, we have to choose an edge which has the least weight out of all. Moving on, we will add the existing edges to its previous vertex forming a subgraph but keeping in mind that we don’t connect all the vertices forming a cycle.

Also, we started with a set having null elements, whenever the key values keep forming part of MST, put the elements in the set to have the final order of the Prim’s Algorithm.

We repeat the same process comparing the least weights and joining the edges together forming a Prim’s MST.

The Time Complexity of Prim’s Algorithm is O(V²)

If deleting vertices in min-heap takes O(log n) then what will be the total time taken for deletion??

It will be O(V log V)

Similarly, if we are traversing adjacency list in order to check vertices adjacent to deleted vertex, it would be O(V+2E).

Where are Prim’s Algorithm used??

• It is used in network designing
• For the production of network cycles
• electrical wiring cables require the use of minimum spanning tree algorithm that too using Prim’s algorithm it will give the sum o the weights of the edges to be least

Let’s take an Example!!

You can take any edge weight you want, Here I am taking first A-B edge forming A — — — B having weight as 1. Now, look for the adjacent edges which are present, you can join either A-D or B-C. I will be joining A-D having weight 5 as it is smaller than the weight of B-C.

So, we have A — — — B and A — — — D so sum of these two are 6. Next, we check for A-C or D-F or D-G. We take D-F having the least weight after comparing. Summing the weight to be 5+1+2 which is 8.

Next we compare between the weights of A-C or B-C or D-G or F-C or F-H, we take F-C having weight 3. Sum is 8+3 which is 11.

Similarly, we compare and observe that A-C or B-C or D-G or F-H or C-E. Here, we have an important thing to observe. A-C and B-C both have 6 weight but when you join the vertices, we observe that it is forming a cycle so we will avoid taking that path and go for the next path.

Then simply C-E will be selected followed by F-H,G-H and G-I will get selected.

So, the final tree formed will be having sum of 36.

Kruskal’s and Prim’s both are a part of Greedy approach algorithm then What is the difference between them??

Kruskal’s Algorithm is minimum spanning tree algorithm which makes use with a different logic to find the MST of a graph. Instead of starting from a vertex, Kruskal’s algorithm will do the sorting of all the edges from the least of all the weight to the maximum of the weights and keeps summing up the minimum edges and just like Prim’s doesn’t allow forming a cycle, here also it doesn’t allow forming a cycle.

Prim’s algorithm can start from any weight, you don’t have to start with the lowest weight. Both the approaches are great approach when it comes to finding the Minimum Spanning Tree of the graph.

So, by concluding here, I would just like to say that Prim’s Algorithm is a very efficient and widely used algorithm because of it’s faster approach in dense graphs and its overall complexity being better than other algorithms.