KRUSKAL’S ALGORITHM (SUMMARY)

Welcome! In this blog, we will be discussing the very famous algorithm named Kruskal’s algorithm and what are its applications, so let us move further with the topic.

First of all, let us get to know what is Kruskal’s algorithm?

So this algorithm is mainly used for finding the minimum cost spanning tree of the graph which uses a greedy approach. Then the question which arises is what is the importance of this algorithm and what applications does it has in real life?

so let us suppose a real-life example that you what to reach a particular destination and there are many paths leading to that particular place, so in such a big network of interconnected roads to find the shortest path Kruskal’s algorithm will be very useful so that an individual can reach the destination as soon as possible.

Now before heading to the actual working of the Kruskal’s algorithm, we need to know what is meant by the minimum cost spanning tree, so a spanning tree is a subset of graph G which is shown below, which has all the vertices covered with a minimum conceivable number of edges, but in spanning-tree it doesn’t consist of cycles.

So how Kruskal’s algorithm works?

so this algorithm basically falls under the class of Greedy algorithms, we start from the edges which have the least weights and we continue to add them until we arrive at our main objective.

so the main key points that we need to put into consideration while solving the minimum cost spanning tree using Kruskal’s algorithm are as follows:

1. We need to sort all of the edges from low to high fashion.
2. Then we need to opt. for the edge which has the most minimal weight and then adds that to the spanning tree following this step if we encounter a situation where it forms a cycle then we need to reject that edge and move to the next minimal edge.
3. we need to continue the #2 step till there are (v-1) vertices in the spanning tree.

Lets us now consider an example:

consider the graph shown below

GRAPH

This graph has 6 nodes and 10 edges.

so we need to proceed with the first step which is to arrange all the edges in a sorted list as per their edge weights and we need to include the edges in the MST in such a way that the included edges do not form a cycle in the tree structure.

So the first edge which we will choose will be the edge EF, as it has the minimum edge weight which is 2.

similarly, we need to continue with the step of adding edges, so the next minimal weight edge will be FD.

so similarly we will also include edge BC and CF to the spanning tree as they do not form any cycle.

but while adding the next minimal edge to the spanning tree which is CD, we will encounter a situation where a cycle will be formed so we need to discard this step.

while following the steps, we will see edge BF also forming a cycle like CD hence we will need to discard this step too.

similarly BD will also be discarded,

so the next minimal edge is AB. As this edge does not form any type of cycle, hence we will include it in the MST structure. hence we will no longer traverse to any more edges in the MST as it’s the last edge in the decreasing value format. hence, the final MST is represented below as shown:

The summation of all the above edges will be equal to 17, which is the least possible edge weight for any possible spanning tree for this particular graph. Hence, that’s all about Kruskal’s algorithm.