Kruskal’s Algorithm

3 min readApr 10, 2022

Minimum Spanning Tree

A minimum spanning tree is one in which the total weight of the edges is kept as low as possible.
CONDITIONS:
1. The spanning tree’s number of vertices is the same as the number of vertices in the original graph.
V’ = V
2. The spanning tree’s number of edges would be equal to the number of edges minus one.
E` = |V| — 1
3. There should be no cycles in the spanning tree.
4. The spanning tree should not be disconnected.

Kruskal’s Algorithm

Kruskal’s Minimum Spanning Tree algorithm is a greedy algorithm to find a minimum spanning tree for a connected weighted graph. Kruskal’s Algorithm finds a subset of the edges from a given graph that covers every vertex in the graph and forms a tree (called MST), with the sum of edge weights being as minimal as possible.

Greedy Technique

Algorithms for optimization problems often follow a number of steps, each with a set of options. In many optimization situations, using dynamic programming to find the best solutions is overkill; simpler, more efficient approaches would serve. A greedy algorithm will always select the option that appears to be the most advantageous at the time. To put it another way, it makes a locally optimum decision in the hopes of obtaining a globally optimal outcome.

Working of Kruskal’s Algorithm

We start with the edges with the lowest weight in Kruskal’s method and keep adding edges until the goal is reached. The following are the steps to implement Kruskal’s algorithm:

Sort all of the edges from lowest to highest weight.
To the spanning tree, add the edge with the lowest weight. If the edge being added forms a cycle, it should be discarded.
Continue to add edges until we’ve reached all of the vertices and after we have joined all the vertices we have a minimum spanning tree.