Kruskal's Minimum Spanning Tree Algorithm | Kruskal's Algorithm | Greedy Algorithm | Data Structure

Definition:
Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach. This algorithm treats the graph as a forest and every node it has as an individual tree. A tree connects to another only and only if, it has the least cost among all available options and does not violate MST properties.

Step 1 - Remove all loops and Parallel Edges
Step 2 - Arrange all edges in their increasing order of weight
Step 3 - Add the edge which has the least weightage
Pseudocode:
KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A

Kruskal's Minimum Spanning Tree Algorithm | Kruskal's Algorithm | Greedy Algorithm | Data Structure