Kruskal’s Algorithm

In this blog, we will discuss Kruskal’s algorithm. Additionally, we will see the complexity, working, example, and implementation of Kruskal’s algorithm.

Basics terms to be known before moving directly towards the algorithm.

Spanning tree-

A spanning tree can be described as the subgraph of an undirected linked graph. It includes all of the vertices at the side of the least possible number of edges. If any vertex is missed, it isn’t a spanning tree. A spanning tree is a subset of the graph that doesn’t have cycles, and it also can’t be disconnected.

Minimum Spanning Tree –

Minimum spanning tree may be described because the spanning tree wherein the sum of the weights of the edge is minimal. the weight of the spanning tree is the sum of the weights given to the rims of the spanning tree.

Now let’s talk about Kruskal’s algorithm.

Kruskal’s algorithm is the concept that is added inside the graph principle of discrete mathematics. it’s miles used to find out the shortest path among factors in a related weighted graph. This set of rules converts a given graph into the woodland, thinking about every node as a separate tree. these trees can simplest link to every different if the edge connecting them has a low value and doesn’t generate a cycle in Minimum Spanning Tree structure. in this academic, you will study more about Kruskal set of rules in detail.


As stated earlier, the Kruskal algorithm is used to generate a minimal spanning tree for a given graph. however, what exactly is a minimum spanning tree? A minimum spanning tree is a subset of a graph with the equal kind of vertices because the graph and edges same to the variety of vertices -1. It moreover has a minimum cost for the sum of all element weights in a spanning tree.

Kruskal’s set of rules types all the rims in increasing order of their area weights and maintains adding nodes to the tree handiest if the chosen facet does now not form any cycle. also, it choices the brink with a minimal price at the start and the edge with a maximum cost at closing. subsequently, you may say that the Kruskal algorithm makes a locally foremost desire, intending to find the global top of the line solution. this is why it’s far referred to as a greedy algorithm.

Steps to algorithm:

• Sort each edge from low weight to high weight.
• We have to edge with minimal weight and it to the Spanning Tree.
• No cycle should be formed.

Some Uses of Kruskal’s Algorithm in real life-

• Telecom services
• Landing Cables
• Local Area Network

Example of Kruskal’s algorithm.

Find the minimum Spanning tree.

Ascending order of the weights.

Step 1 — Join AB as it has lowest weight.

Step 2 — Add DE as it has second lowest weight.

Step 3- Now, pick the edge BC, as no cycle is formed.

Step 4 — Join CD with weight 4.

Step 5 — Now, AE will not be added as after joining AE, a cycle will be formed.

Step 6 — Adding AD will also create the cycle, so discard it.

Final MST obtained by using Kruskal’s algorithm-

Cost = AB + DE + BC + CD = 1 + 2 + 3 + 4= 10.

Complexity –

Time complexity is O(V logV) or O(E logE).

V= Number of vertices.

E= Number of edges.