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.
Demo
Resources