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 vs Kruskal
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

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

Additional Reading: When to use kruskal’s algorithm over prim’s method

Leave a Reply

Your email address will not be published. Required fields are marked *