Kruskal's Algorithm

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

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