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.
Kruskal’s algorithm for MST
Kruskal's Algorithm helps to determine the minimum spanning tree for a connected weighted graph. It determines the subset of edges that can visit all of the graph's vertex. Instead of finding a global optimum, this algorithm finds an optimal solution at each stage.
The algorithm’s steps are listed below.
👉 Create a forest. The forest's graphs are all individual trees. A forest is a group of disjoined trees. We can obtain it by removing the root node and the edges that link root nodes to the first level node.
👉 Create a priority queue that includes all of the graph's edges.
👉 If the priority queue is not empty, repeat steps 4 and 5.
👉 Remove an edge from the priority queue.
👉 Add the edge from step 4 to the forest if it joins two trees; otherwise, discard it.
E.g. Consider a graph with four vertices (A, B, C, D) and the following weighted edges: AB (3), AC (1), BC (4), CD (2), BD (5).
To find the MST using Kruskal's algorithm:
1. Sort the edges in ascending order based on their weights: AC (1), CD (2), AB (3), BC (4), BD (5). This is done because we always pick the smallest edge.
2. Pick AC as it has the minimum weight.
3. Next, We pick CD by the same criteria. Also, at each step, we need to keep checking whether it is forming a cycle.
4. Continue to do this till we reach v-1 vertex. Connecting AB completes our minimum spanning tree.
At this point, we have included three edges (AC, AB, CD) in the MST, which connects all the vertices without forming any cycles. Thus, the resulting minimum spanning tree with a total weight of 6.
Let’s now learn the difference between Kruskal and Prim's algorithms.
Key Differences between Prims and Kruskal Algorithm
The difference between Kruskal and Prim's algorithms is given below.
|Prim’s Algorithm||Kruskal’s Algorithm|
|From any vertex in the graph, it begins to construct the Minimum Spanning Tree.||It begins to construct the Minimum Spanning Tree from the vertex in the graph with the minimum weight.|
|To determine the shortest distance, it travels through each node more than once||It only visits one node.|
|The Prim algorithm produces connected components and only functions on connected graphs.||The Kruskal algorithm is capable of creating forests (disconnected components) at any time and can also operate on disconnected components.|
|It constructs the minimum spanning tree beginning from the root vertex.||It constructs the minimum spanning tree by starting with the edge with the lowest weight.|
|It runs faster in dense space.||It runs faster in sparse space.|
|The time complexity of Prim’s algorithm is O(V^2), where V is the number of vertices, and it can be reduced to O(E log V) by applying Fibonacci heaps.||The time complexity of the Kruskal algorithm is O(E log V), where V is the total number of vertices.|
These are some of the major difference between Kruskal and Prims algorithms.
Frequently Asked Questions
Q. Why do we use the Kruskal algorithm?
We use the Kruskal algorithm to find the minimum spanning tree in a connected graph. It helps in finding the shortest path to connect all nodes (vertices) while avoiding cycles, often used in network design and optimization problems.
Q. Why is the Kruskal algorithm better?
The Kruskal algorithm is preferred because it guarantees the creation of a minimum spanning tree efficiently. It's easy to understand, works well with large graphs, and doesn't require the graph to be connected initially.
Q. What is the application of the Kruskal algorithm?
The Kruskal algorithm is applied in various fields, including network design, transportation planning, and circuit design. It helps find the minimum spanning tree, reducing costs and optimizing connections in networks.
Q. Can Prim's algorithm have multiple solutions?
No, Prim's algorithm for finding a minimum spanning tree in a weighted graph does not have multiple solutions. The algorithm guarantees the construction of a unique minimum spanning tree for a given graph.
Q. Does Prims and Kruskal give the same output?
Prim's and Kruskal's algorithms do not always give the same output. While both algorithms aim to find a minimum spanning tree, the specific edges are chosen, and the order of their selection may differ between the two algorithms.
Q. Does Prims or Kruskal algorithm work with negative weights?
Kruskal's algorithm can handle graphs with negative weights. However, Prim's algorithm, as commonly used, assumes non-negative edge weights and may not work correctly with negative weights.
In this article, we have extensively discussed the Spanning Tree, Minimum Spanning Tree, how to find MST using Kruskal's and Prim's Algorithm, and the difference between Kruskal and Prims algorithm. I hope you enjoyed this blog on the Difference between Kruskal and Prims algorithms.
If you want to learn more, check out our articles on Minimum weight cycle in an undirected graph, Construct the Full K-ary Tree from its Preorder Traversal, Regular and Bipartite graphs, and Planar and Non-Planar Graphs.