Prim’s vs Kruskal Algorithm
Prim’s vs Kruskal Algorithm
In this article we will talk about Prim’s vs Kruskal minimum spanning tree algorithms.
Prim’s and kruskal’s minimum spanning tree algorithms are compared here in this article. Both algorithms are used to find minimum spanning tree of the graph. They follow the greedy approach to solve the problem.
Prim’s algorithm will build a solution from a random vertex by adding the next cheapest vertex, which is presently not in the solution but is related to it by the cheapest edge.
If a cycle is not created, Kruskal’s method will build a solution from the cheapest edge by adding the next cheapest edge. Although working principle of both the algorithm is different, they generate the identical tree for any given graph
| Prim’s Algorithm | Kruskal’s Algorithm |
| Prim’s algorithm always chooses the next edge which is a neighbour of vertices in partially generated solution. | The Kruskal algorithm always chooses the edge having a minimum weight. |
| Selection of the route is based on vertices | Selection of the route is based on edges |
| Prim’s algorithm ensures that partial solution is always a tree. | In Kruskal’s algorithm, a partial solution can be a forest. |
| Sorting of edges is not required. | Sorting of edges is compulsory. |
| Solution is initiated with a node | Solution is initiated with an edge |
| Picking up next edge requires finding an edge with minimum cost from a set of adjacent edges. | As edges are always sorted, minimum cost edge can be chosen in O(1) time. |
| Prim’s algorithm is a better choice for the dense graph. | Kruskal’s algorithm is a better choice for the sparse graph. |
| With the help of Fibonacci heap, Prim’s algorithm has O(E + V log V) amortized running time | Kruskal algorithm runs in O(E log V) time, which is greater then Prim’s method |
Some Popular Problems Solved by Greddy Algorithm
Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :
- Binary Knapsack Problem
- Fractional Knapsack Problem
- Job Scheduling Problem
- Activity Selection Problem
- Huffman Coding
- Optimal Storage on Tapes
- Optimal Merge Pattern
- Prim’s Algorithm
- Kruskal’s Algorithm
- Dijkstra’s Algorithm
Additional Reading: When to use kruskal’s algorithm over prim’s method