kruskal’s algorithm

4 min readApr 10, 2022

Thank you for visiting! In this blog, I’d want to discuss what Kruskal’s algorithm is, how it works, where it’s used, and how it’s used.

Let’s start with a definition of Kruskal’s algorithm.

So, in a network using a greedy approach, we utilize Kruskal’s technique to discover the minimal cost of spanning tree. Now the question is, what do we do with that information once we’ve found the lowest cost? How can it be of assistance to us?

What is greedy algorithm?

The Greedy strategy is the simplest and most direct of all the algorithmic methodologies. In this process, the decision is made on the basis of currently available data without considering the long-term consequences of the current decision.

Greedy algorithms make together an answer piece by piece, picking the next portion in such a way that it provides a quick advantage or solution. This process never revisits previously made decisions. Greedy tactics are simple to use and, in the vast majority of circumstances they are quite effective and useful. As a result, we can define Greedy algorithm as an algorithmic worldview that is based on the heuristic that follows. At each stage, make the best local option possible in the hopes of discovering the best global solution.

What is the MST (minimum spanning tree)?

A spanning tree is a subset of Chart G that covers all of the vertices with the very fewest amount of edges possible. As a result, a spanning tree has no cycles and cannot be detached or reversed.

We can deduce or minimize from this definition 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 detached chart doesn’t have a spanning tree.

How does Kruskal’s algorithm work?

It belongs to a category of algorithms known as greedy algorithms. We begin with the edges with the least weight and gradually increase the number of edges until we reach our objective.

The following are the tools used to perform Kruskal’s calculation:

1) Sort all of the edges from lightest to heaviest weights. That is in ascending order.

2) Add the edge with the least amount of weight to the spanning tree. If adding the edge resulted in a cycle, this edge should be rejected and not to be used any further.

3)Continue to add edges until all vertices have been reached.

there are 6 nodes and 11 edges in fig 0.1

Step 1:

Remove all parallel edges and loops from the graph, then choose the edge with the least weight from the parallel edges.

Step 2:

Next, make a set of edges and weights, then arrange them in increasing order of weightage (cost).

Step 3:

At this point, we’ll start adding edges to the diagram, starting with the one with the smallest weight. Throughout, we’ll keep an eye on the spanning properties to make sure they’re in perfect working order. If the spanning tree attribute is broken as a result of adding one edge.

Step 4:

The smallest cost is 2, and the edges B,D, and D,T are included. We’ll include them. Because adding them does not violate spanning tree characteristics, we may move on to the next edge determination step.

The next cost is 3, and the edges A,C, and C,D are connected.

We’ll toss it out and avoid any edges that form a circuit.

Step 5: We can observe that edges with cost 5 and 6 form circuits as well. We ignore them and go on our way. Only one more node needs to be added now.