Prim’s Algorithm
Hi guys!
This blog talks about Prim’s algorithm. If you want a quick crash course on this topic stick around.
Prim’s Algorithm is a greedy algorithm which is used to find the minimum spanning tree of a graph.
History
This algorithm was developed by mathematician Vojtech Jarnik in 1930. He was a Czech mathematician .It was later rediscovered and republished in 1957 by Robert C. Prim, a Computer scientist. This is why the algorithm is also called Jarnik’s algorithm.
What is a Minimum spanning tree?
A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Essentially what this means is that it is a tree which contains all the vertices of the given weighted undirected graph and the total edge weight is the minimum.
What is a Greedy Algorithm?
A greedy algorithm is an algorithm which makes optimal choices at each step instead of considering the overall optimal way to solve the problem.
The greedy method is a very intuitive way to solve the problem but as it fails to consider the overall most efficient method, it is best suited for problems in which the solution is picking the local optimal choice.
Some other greedy algorithms in graphs are Kruskal’s Minimum spanning tree algorithm, Boruvka’s Minimum spanning Tree algorithm, Dijkastra’s minimum spanning tree algorithm.
Working of the Algorithm
Prim’s algorithm can be broken down into 3 steps.
Step 1: Remove all self loops and parallel edges. For parallel edges, remove the one with the higher weight.
Step 2: Pick an arbitrary node as the starting point. Initially, all distance of the other vortex from that point should would be INFINITE.
Step 3: Update the distance of the adjacent vortex from the node we are currently at. Go to the next node which has the minimum weight available.
Repeat step 3 till all the nodes have been visited.
Let us take an example to understand this in a better way.
Let us take this graph and use prim’s algorithm on it.
For the first step we have to remove all the self loops and parallel edges. Node B has a self loop and vertices F and G have parallel edges. For the parallel edges, we keep the one with the lower weight, in this case the one with the edge weight of 3.
Let us start at Node A.
All the other nodes currently have infinite(INF) distance from A. Now we update the distance of the adjacent nodes. Node B and F are adjacent to it.
Now our next node should be the one with the least weight. So we move to Node B. Node C and F are adjacent to B so we update their value.
The above figure shows the minimum spanning tree as traverse through the graph.
The above table shows all the available paths and the edge weight for the path. B,C has the least edge weight so we go to node C.
The nodes adjacent to C are E and D. We update their distance.
Figure 2.1 shows the available paths at this Node. C,E has the least edge weight so we move from C to E.
Figure 2.2 shows all available paths at this point. We pick E,F path as it has the minimum weight.
Figure 2.3 shows all s available paths. Notice how A,F and B,F are no longer available. This is because we are at Node F and we already visited Node A. Thus we can no longer use those paths. We move to node G from F.
Figure 2.4 shows all available paths. We move from G,D and since we visited all the nodes we end the algorithm here. The path we followed is the minimum spanning tree.
The above figure shows the final minimum spanning tree formed by using this algorithm.
Any other path which covers all the vertices will have more edge weight than this.
This video will help you understand the algorithm better.
Time Complexity
The time complexity for this algorithm varies as we use different data structures. For adjacency matrix the time complexity is O(V²).
When using binary heap along with adjacency list, the time complexity is O(E log V).
For Fibonacci heap along with adjacency list, the time complexity is O(E+V logV).
Here E is the number of edges present and V is the number of vertices of the graph.
Prim’s algorithm vs Dijkstra’s Algorithm
Dijkstra’s algorithm is another greedy algorithm. Prim’s algorithm gives the minimum spanning tree while Dijkstra’s algorithm gives the shortest path tree.
In some cases, the shortest path tree will be the same as the minimum spanning tree.
Prim’s algorithm is restricted to undirected graphs while Dijkstra’s algorithm can work for both types of graphs.
Prim’s algorithm can work with negative edge weights while Dijkstra’s algorithm will not work with negative edge weight.
