Kruskal’s Algorithm for Minimum Spanning Tree

Kruskal’s Algorithm is a Minimum Spanning Tree Algorithm. Now, the question arises what is the Minimum Spanning Tree? — A Minimum Spanning Tree is used to minimize the weights or lengths of the edges of the tree.

Also, A minimum spanning tree of a connected graph is a subset of the edges that includes every vertex.

Comparing Spanning Tree & Minimum Spanning Tree

Kruskal’s Algorithm is used to build the minimum spanning tree of an undirected edge-weighted graph by adding edges one by one into a growing spanning tree. Also, Kruskal’s algorithm picks the edges with a minimum cost at first & the edge with a maximum cost at last. Hence, you can say that the Kruskal algorithm makes an optimal choice which is why it is called a Greedy Algorithm.

How to Find Minimum Spanning Tree Using Kruskal’s Algorithm?

Step 1: Sorting all the graph edges in the non-decreasing order of their weight.

Step 2: Picking up the smallest edge & start adding edges to the Minimum Spanning Tree(MST). Check if it is forming a cycle with the spanning tree or not. If the cycle is not built, enter any other edge.

Step 3: Repeat Step 2 until the (V-1) edges on the expandable tree.

Consider the following example:

Therefore, Minimum Spanning Tree with Total Cost = 1 + 2 + 3 + 5 = 11

In Kruskal’s Algorithm, At each iteration, we will be going to select the lowest weight edge. So, we will start with the lowest weighted edge first which is the edge with weight 1.

• After selecting the second-lowest weighted edge which is the edge with a weight of 2. Hence, these two edges are totally disjoint.
• Now, the next aspect may be the third-lowest weighted part i.e edge with weight 3, which connects disjoint portions of a graph.
• Now, we are not allowed to pick the edge with weight 4 because that will going to create a cycle & we can’t have cycles. So, we will select the fifth-lowest weighted edge which is an edge with a weight of 5.
• The cycles will be created if we use the other two edges so we will ignore them. In the end, We will get a value of a minimum spanning tree with a Total cost of 11.

Kruskal’s Algorithm Pseudocode

Any small tree algorithm revolves around checking whether adding an edge creates a loop or not.

Time Complexity

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

The Time Complexity of Kruskal’s algorithm is O(E log V), Here V is the no. of vertices.

Real-life Application of Kruskal’s Algorithm:-

1. In order to layout electrical cables & TV Networks.
2. In Computer Network (LAN Connection)
3. It is used in Geographical Maps.