How it works?

Union-find bir parent dizisi tutar. Her köşe kendi kökü olarak başlar. Her şeyi iki işlem yönetir:

• find(x): bir köke (kendi kendisinin ebeveyni olan bir köşe) ulaşana kadar parent bağlantılarını takip edin. İki köşe, aynı kökü paylaştıklarında birbirine bağlıdır.
• union(a, b): bir kökü diğerine yönlendirerek iki kümeyi birleştirin.

Kruskal Algoritması:

1. Kenarları en küçük ağırlıktan en büyüğe doğru işleyin.
2. Her kenar için uç noktalarının köklerini find ile bulun. Eğer farklılarsa, kenar iki ayrı parçayı birleştirir: onları union ile birleştirin ve ağırlığını toplama ekleyin.
3. Eğer kökler aynıysa, kenar bir döngü oluşturacaktır, bu yüzden onu atlayın.

Her kenar işlendikten sonra, seçilen kenarlar MST'yi oluşturur (bağlantılı bir grafik için bunlardan tam olarak n - 1 tanesi).