Kruskal’s Algorithm

A very good morning geeks, today we’re discussing about a greedy algorithm that is used to find out a minimum spanning trees. So let’s talk about what a minimum spanning tree is:

Minimum Spanning Tree :

Kruskal’s Algorithm is a minimum spanning tree algorithm where you find the minimum number of spanning trees, and to know this lets quickly define what spanning trees are. Spanning tree is a subgraph of a graph that’s connected and undirected and a minimum spanning tree is a graph whose sum of weights of edges is minimum. Kruskal’s Algorithm is also greedy because at every step it adds the next smallest weight that will not form a cycle.

The steps for finding MST using Kruskal’s algorithm goes as follows:

1. Sort all the edges in non-decreasing order of the weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far, if cycle is not formed, include this edge. Else, discard it.
3. Repeat step 2 until there are (V — 1) edges in the spanning tree. (Assume there’s “V” vertices).

Let’s discuss this with an example :

Step 1 : Let’s start with the smallest edge which is BE.

Step 2 : Then let’s start with the next smallest edge which would be AC and EF.

Step 3 : Look for the next smallest edge which will be BC and EG so on and so forth till the number of edges is V — 1 where V is the number of vertices in the graph which will end with the next smallest edge which is CD, we cannot connect FG because then it’ll start an internal loop.

Step 4 : The resultant tree will be the minimum spanning tree.

Let’s look at the Pseudocode :

Pseudocode:

This is how the algorithm works :

1. You sort all the edges in ascending order of weight from low weight to high weight.
2. You calculate the edge with the smallest weight and add it to the spanning tree. If a cycle is being created by adding the edge then remove that edge. And how do we know is a cycle is being created or not, we check if the vertices are already part of the tree.
3. Keep adding the edges until all the vertices are used.

Time Complexity:

The overall time complexity is either O(ElogE) or O(ElogV). The best case time complexity is O(ElogV) and the worst case time complexity is O(ElogE).