Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
Steps for finding MST using Kruskal’s algorithm
Steps for finding MST using Kruskal’s algorithm
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far.
2.a. if the cycle is not formed, include this edge.
2.b. else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
Example:
