Motivation

Kruskal, seçilen kenarlardan oluşan ve büyümekte olan ormanı bir union-find yapısında tutar. Bir kenarı güvenli bir şekilde eklemek için, iki uç noktanın halihazırda aynı kümede olup olmadığını kontrol eder (bu bir döngü oluşturur).

Neden Kruskal öğrenilmeli?

• Gerçek MST'ler: ağ tasarımı, kümeleme ve minimum maliyetle kablo veya yol döşeme.
• Union-find: bilgisayar biliminin her yerinde karşımıza çıkan, bağlantısallığı izlemek için kullanılan güzel ve yeniden kullanılabilir bir yapı.
• Açgözlü (greedy) doğruluk: her zaman en ucuz güvenli seçeneği almanın küresel optimumu sağladığı başka bir örnek.

Bir grafın tüm minimum yayılan ağaçları aynı kenar ağırlığı çoklu kümesini kullanır, bu nedenle toplam ağırlık (ve en büyük kenar) benzersizdir.