Kruskal's Algorithm

Learn via video course
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
Topics Covered


Kruskal's algorithm is a greedy algorithm in graph theory that is used to find the Minimum spanning tree (A subgraph of a graph G(V,E)G(V,E) which is a tree and includes all the vertices of the given graph such that the sum of the weight of the edges is minimum) of a given connected, weighted, undirected graph.

In case, the graph is not connected, on applying Kruskal's algorithm we can find the MST of each connected component.


Complexities of the Kruskal's Algorithm

  • Time Complexity :O(Elog(E))O(E*log(E))
  • Space Complexity:O(E)O(E)

Introduction to Kruskal’s Algorithm

Suppose that there are some villages in a town, you being the Mayor of the town want to visit all the villages but you have very little time for it.

So you will be interested in visiting the villages in such a way that the total distance covered by you during the visit is minimum possible. Isn't it.?

If you try to formulate the above problem in terms of graph theory, by considering villages as the vertices, roads connecting them as the edges, and the distance of each road as the weight of the corresponding edge.

Kurskal's algorithm will help you in this case because it is used to find the minimum spanning tree (MST) of any given connected, weighted, undirected graph. Before discussing any further details of Kruskal's algorithm let's see what is meant by a Minimum spanning tree of a graph.

A spanning tree is a subgraph of a connected, undirected graph such that it is a tree and it includes all the vertices. So a minimum spanning tree would correspond to a spanning tree with the minimum weight. Where the weight of a spanning tree is the sum of the weight of the edges present in it.

For Example:

The below-given image shows a graph GG with 6 vertices and 9 edges graph with 6 vertices and 9 edges

This graph can have multiple spanning tree some of which are shown below with their respective weights. multiple spanning tree

But they can not be considered as minimum spanning trees as there exists at least one spanning tree with an even smaller sum of edge weights. The MST of the graph is - minimum spanning tree with sum 17

The MST of the given graph has a weight of 17, which means that we can't form any other spanning tree of graph GG whose weight is less than 17.

Kruskal's Algorithm Implementation

The main idea of Kruskal's algorithm to find the MST of a graph GG with VV vertices and EE edges is

  • to sort all the edges in ascending order according to their weights.
  • Then select the first V1V-1 edges such that they do not form any cycle within them.

One thing that can be observed here is, that for any graph with VV vertices, we are interested in including only V1V-1 edges as part of the MST. It is because we need only that many edges to include all the vertices.

Let us understand how Kruskal's Algorithm works by the following algorithm and example

Algorithm of Kruskal's

For any graph, G=(V,E)G=(V,E), finding an MST using Kruskal's algorithm involves the following steps -

  • Sort all the edges of the graph in ascending order of their weights.
  • Check the edge with minimum weight, if including it in the answer forms a cycle discard it, otherwise include it in the answer.
  • Repeat the above step until we have chosen V1V-1 edges.

Example of Kruskal's Algorithm

Let's say we want to find the MST of the underlying connected, weighted, undirected graph with 66 vertices and 99 edges- Examples of Kruskal algorithm

Now as per the algorithm discussed above, to find the MST of this graph -

  1. We will write all the edges sorted in ascending order according to their respective weights
  2. Then we will select the first V1=5V-1=5 edges which do not form cycles.
  • Step 1 - Sort the edges in ascending order. Here is the list after sorting.

  • Step 2 - Choose 5 edges from starting which do not form a cycle.

    • Checking edge 454\Longleftrightarrow 5 - This is the first edge so it can't form any cycle hence including this in result -

      checking edge between 4 and 5

    • Checking for edge 343\Longleftrightarrow 4 - Including this edge in the result does not form any cycle. checking edge for 3 and 4

    • Checking for edge 232\Longleftrightarrow 3 - Again including this edge in the result does not form any cycle. checking for edge 2 and 3

    • Checking for edge 353\Longleftrightarrow 5 - Including this edge in the result forms a cycle 34533 \rightarrow 4 \rightarrow 5 \rightarrow 3, hence not including this in the result. checking for edge 3 and 5

    • Checking for edge 565\Longleftrightarrow 6 - Including this edge in the result forms a cycle 45644 \rightarrow 5 \rightarrow 6 \rightarrow 4, hence not including this in the result. checking for edge 5 and 6

    • Checking for edge 252\Longleftrightarrow 5 - Including this edge in the result forms a cycle 234522 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2, hence not including this in the result. checking for edge 2 and 5

    • Checking for edge 121\Longleftrightarrow 2 - Including this edge in the result does not form any cycle. By including this, we have included 5 edges so now the result will correspond to the minimum spanning tree.

After including all 55 edges, the MST will look like this -

include all edge

So the weight of MST can be calculated as 7+3+3+2+2=177+3+3+2+2=17.

Pseudocode of Kruskals Algorithm

Code Example of C/C++, Python

To efficiently check whether including an edge forms a cycle or not, we will use an already discussed concept i.e.i.e. Disjoint-Sets. We will proceed as per the pseudocode and algorithm discussed above, i.e.i.e. firstly sorting the list of edges and then including V1V-1 edges that do not form cycles. Find function of DSU will be used before including any edge in the MST to check if both the endpoints (nodes) of the edge belong to the same set or not. If they do not belong to the same set, we will include that edge in the MST as including the edge is not forming any cycle. Now we will use the union function of DSU to merge the two disjoint sets. Before going into the code, let's see its blueprint -

Variables -

  • VV - A global variable that will denote the number of vertices present in the graph.
  • EE - Again a global variable denoting the count of edges present in the graph.
  • edgesedges - A list of edges that will be sorted and then used in the Kruskal algorithm.

Method -

  • MST_KruskalMST\_Kruskal - A function that is responsible to find the MST of a given graph implemented as discussed in the algorithm and pseudocode.

Future-Proof Your Coding Skills! Join Our Best DSA Course for In-Depth Algorithmic Understanding. Enroll Now!

C/C++ Implementation of Kruskal's Algorithm

Java Implementation of Kruskal's Algorithm

Complexity Analysis

  • Time Complexity -
    • Sorting of EE edges costs us O(Elog(E))O(E*log(E)) time.
    • For each edge, we are using the Union-Find algorithm which costs us O(Eα(V))O(E*\alpha(V)) time.
    • As discussed in DSU, for practical values of VV, i.e.i.e. V1080V\leq 10^{80} we can write O(Eα(V))O(E*\alpha(V)) as O(E)O(E) because O(α(V))O(\alpha(V)) \simeq O(1)O(1).
    Hence, the overall time complexity is O(Elog(E)+E)O(E*log(E)+E) \simeq O(Elog(E))O(E*log(E))
  • Space Complexity - We are using a List/Vector to store the EE edges of the given graph so the space complexity is O(E)O(E).

Applications of Kruskal's Algorithm

MST's which can be found using the Kruskal algorithm has the following applications -

  • In-network designing, finding MST tells you the minimum amount of wire needed to connect all the nodes (servers).
  • Approximation of NP-Hard problems, like we can use MST to solve the traveling salesman problem.
  • It is used in autoconfig protocol for ethernet bridging, which helps to avoid cycles in a network.
  • All other graph theory problems where we need to visit all the vertices with minimum cost.

Become a master of data structures with our Data Structures in C++ Free Course. Start your journey today!


  • In this article, we have learned what is meant by the spanning trees of a graph and what is the minimum spanning tree with the help of examples.
  • We have seen Kruskal's algorithm which is a greedy algorithm to find an MST of any given weighted, undirected graph.
  • At last, we have analyzed its time and complexity and space complexity and seen some of its major applications.