Prim’s Algorithm is a greedy algorithm used for finding a minimum spanning tree (MST) in a connected, undirected graph.
• Similar to Kruskal’s Algorithm, Prim’s Algorithm builds the minimum spanning tree step by step, always selecting the edge with the minimum weight.
Steps for finding MST using Prim’s algorithm:
- Initialize the minimum spanning tree with a vertex chosen at random.
- Find all the edges that connect the tree to new vertices, find the minimum and add it to the MST.
- Keep repeating step 2 until we get a minimum spanning tree
for example:
Step 1 – First, we have to choose a vertex from the above graph. You can choose any. Let’s choose A.
Step 2- Find all the edges that connect the tree (vertex A) to new vertices, find the minimum and add it to the MST.
There are two edges from vertex A that are AB with weight 4 and AD with weight 10. Among the edges, the edge AB has the minimum weight. So, add it to the MST.
Now, again, choose the edge with the minimum weight among all the other edges and add it to the MST. In this case, the edges BD and BC are such edges. BC has minumun weight so we add it. Also consider the edge AD if it has minimum weight than these edges add it to the MST.
Now, again, choose the edge with the minimum weight among all the other edges and add it to the MST. In this case, the edge CD is such edge. Also consider the edges AD, BD if any has minimum weight than these edges add it to the MST. Here BD has minimum weight so we add it.
Now, again, choose the edge with the minimum weight among all the other edges and add it to the MST. In this case, the edge DE is such edge. Also consider the edges AD, CD if any has minimum weight than these edges add it to the MST. Here DE has minimum weight so we add it.
Note:- if we add AD or CD it will form cycle or loop that discards the property of MST so we discard these edges.
So, this is the minimum spanning tree of the given graph. The cost of the MST is given below –
Cost of MST = 4 + 2 + 1 + 3 = 10 units.
Applications of Prim’s Algorithm:
- Network Design
- Cluster Analysis
- Image Segmentation
- Robotics
