Difference b/w Kruskal's and Prim's algorithm when solving MST

Two algorithms that are very popular for finding the minimal spanning tree (MST) in a graph are Kruskal’s algorithm and Prim’s algorithm. These algorithms are designed to solve almost the same problems following different patterns.

Kruskal’s algorithm

Kruskal’s algorithm finds the minimum spanning tree (MST) and follows a greedy approach to weighted undirected graphs. It is particularly useful for finding MSTs in sparse graphs, where the number of edges is much smaller than the number of vertices. In these cases, Kruskal’s algorithm is much faster than other algorithms.

  • Step 1: Kruskal’s algorithm starts with a non-descending order, sorting all the graph’s edges according to their weight.

  • Step 2: Add edges to the MST one at a time while ensuring that none of the new edges form a cycle.

The following widget demonstrates the Kruskal's algorithm:

1 of 5

Prims's Algorithm

Prim’s algorithm also finds the minimum spanning tree (MST) and follows a greedy approach in a weighted graph. It is particularly useful for finding MSTs in dense graphs, where there are few edges relative to the number of vertices.

The simple steps of Prim's algorithm are as follows:

  • Step 1: We can start with an arbitrary vertex as the minimum spanning tree's root.

  • Step 2: Keep adding the nearest vertex connected to the tree.

  • Step 3: Repeat step 2 until the minimal spanning tree contains all of the vertices.

1 of 5

Key differences between Prim's and Kruskal's

Prim's Algorithm

Kruskal's Algorithm

Minimum Spanning Tree (MST) is constructed from any vertex in the graph.

Minimum Spanning Tree (MST) is constructed from a vertex with minimum weight in the graph.

Vertices are traversed more than once to find MST.

Vertices are traversed only once to find MST.

The time complexity for Prim's algorithm is O(V2), where V is the number of vertices.


The time complexity for Kruskal's algorithm is O(E log V), where V is the number of vertices.

All graph elements must be connected.

All graph elements may not be connected.

Prim's shows better performance in the case of the dense graph.

Kruskal's shows better performance in the case of the sparse graph.

It uses the List data structure.

It uses the Heap data structure.

Free Resources

HowDev By Educative. Copyright ©2025 Educative, Inc. All rights reserved