Kruskal’s Algorithm

Welcome everyone, I want to talk about what is Kruskal’s Algorithm, how it works and where do we use it. So, let’s get started

First and foremost, what is Kruskal’s algorithm?

In a graph using a greedy approach, Kruskal’s technique is used to discover the minimum cost of a spanning tree.

After Finding the Minimum cost of Spanning tree, where do we apply that, how can we analyze the information?

To understand this, I’ll give you a real-life example

Basically, when you want to travel to some other place from your location, there might be multiple ways to reach your destination, Here the Kruskal’s law comes into action to give you the shortest route

To understand all these, first we need to understand what greedy method is

Greedy is an algorithmic model that assembles a solution one by one, constantly opting for the next component that provides the most evident and instant benefit. Greedy is best suited to issues when picking locally optimal also leads to a global optimum.

What is Minimum spanning tree (MST)

A spanning tree is a subset of Chart G that covers all vertices with the fewest amount of edges possible. As a result, no cycles exist in a spanning tree, and it cannot be disconnected.

We can deduct from this assumption that each related and undirected Chart G contains at least one spanning tree. Because it can’t be stretched across all of its vertices, a disconnected graph doesn’t have a spanning tree.

How Kruskal Algorithm Works?

It belongs to a category of algorithms known as greedy algorithms, which seek for the local solution in the hopes of discovering the best solution.

We begin with the edges with the lowest weight and gradually increase the number of edges until we reach our goal.

Steps for Kruskal’s Algorithm:

1) Sort all of the edges from low to high.

2) Choose the edge with most minimum weight and add it to the spanning tree. Discard this edge if it created a cycle by adding it.

3) Keep adding edges until we’ve reached all the vertices.

Let’s Consider this graph

The following graph has 6 nodes and 11 edges.

Step 1:

Eliminate all the loops and parallel edges from the given graph

Step 2:

Sort the edges and weights in the ascending order of the weightage (cost)

Step 3:

Now, we start adding edges to the graph from the minimum weights

Overall, we should keep checking that spanning properties should remain same

If the spanning properties violate, then we should not consider that edge or we should not include the edge

Step 4:

The minimum or smallest weight is 2 which includes the edges B, D and D, T

So, we sum them and adding them doesn’t violate spanning-tree properties

So, we move to the next edge

Next weight (cost) is 3 which edges are A, C and C, D we sum them again

The next weight is 4 if we sum them up. It will create a cycle.

so, we discard or eliminate it and we should move on to next weight

Step 5:

Up on to the next step, we add 5 and 6. These 2 are making cycles.

So, we eliminate or discard them

Now we are left only with one node to be added. Between 2 Weights.

We go with the minimum one

This is the minimum cost spanning tree

Pseudo code of Kruskal’s law