Introduction
When it comes to finding minimum spanning trees in weighted graphs, two popular algorithms are Kruskal's algorithm and Prim's algorithm. While both algorithms aim to achieve the same goal, their approach and the order in which they select edges to construct the minimum spanning tree differ. Understanding the differences between Kruskal's and Prim's algorithms is crucial for selecting the most appropriate method for a given scenario.
Prim's algorithm starts by choosing a root vertex and then moves through adjacent vertices. In contrast, Kruskal's algorithm creates the minimum spanning tree by beginning with the smallest weighted edge.
In this blog, we will learn the difference between Kruskal and Prims algorithms used for finding Minimum Spanning Tree in a graph.
Prim’s algorithm for MST
Prim's algorithm helps to find the minimum spanning tree from a graph. It finds the collection of edges that includes every vertex in the graph. It also decreases the sums of the edge weights. Additionally, this approach starts with the root node and checks each step's nearby nodes as well as connected edges. Also, it chooses the edges with fewer weights that don't result in cycles.
The algorithm's steps are listed below.
- Choose a root vertex or a starting vertex.
- Repeat steps 3 and 4 up until there are fringe vertices.
- Choose an edge with a minimum weight that connects the tree vertex and the fringe vertex.
- Add the selected edge and vertex to the minimum spanning tree.
E.g. Consider a graph with five vertices: A, B, C, D, and E. Having the following weights:
To find the MST using Prim's algorithm:
1. Start with an arbitrary vertex, let's say A.
2. Add vertex A to the MST.
3. Consider all the edges connected to the MST. Choose the edge with the smallest weight. In this case, AC has the smallest weight (1), so we add edge AC to the MST.
4. Consider the edges AB, BC, CD and CE. The most important thing to remember in Prim’s algorithm is that you need to consider the previous weights too. Choose the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST. BC has the smallest weight (3), so we add edge BC to the MST.
5. Now CE has the minimum weight among all the previous left weights. AB would have been possible, but that would make a cycle in the graph, so ignore it.
6. Finally, we connect BD as it has the minimum weight and does not form any cycle.
At this point, all vertices are now connected in the MST, and the total weight of the MST is 1 + 3 + 4 + 2 = 10.
Let’s now learn Kruskal’s algorithms for finding MST of a graph. Also, the difference between Kruskal and Prims algorithms.
8+ registered 