Kruskal's Algorithm

A Greedy algorithm that grows a forest of minimum spanning trees and eventually combines them into one MST:

• Sort all edges (in ascending order, based on weight)
• Start with an empty minimum spanning tree $T = \{\}$.
• Pick the smallest edge and add it to $T$.
• Add next smallest edge to $T$ unless it creates a cycle.
• Repeat the last step until $(N – 1)$ edges were added.