Minimum ağaç, tüm düğümleri en az toplam kenar ağırlığıyla bağlantı kurmak için kullanılır. Bu ağaçlar bulmak için iki ortak algoritma Kruskal ve Prim'in algoritmalarıdır. Her ikisi de yaklaşım ve uygulama açısından farklıdır.

Kruskal'ın Algoritma

Kruskal'ın grafikteki her kenarlar ağırlıkla algoritmaya benziyor. Daha sonra kenarları en küçük ağaçtan başlayarak, döngülerin oluşturulmasını sağlamak. Bu işlem tüm düğümlerin birbirine bağlı olana kadar devam ediyor.

Algoritma özellikle sparse grafikler için etkilidir. Bir kenar eklemek bir döngü oluşturabilir olup olmadığını verimli bir şekilde kontrol etmek için bir disjoint set veri yapısını kullanır.

Prim's Algorithm

Prim’in algoritması, ağacın yeni bir düğüme bağlandığı en küçük kenar ekleyerek keyfi bir node'den başlar. Tüm düğümler dahil olana kadar devam eder.

Bu yöntem genellikle yoğun grafikler için tercih edilir. Bir sonraki kenarı en az ağırlık ile verimli bir şekilde seçmek için öncelikli bir kuyruk kullanır.

Karşılaştırma ve Uygulama

Her iki algoritma da minimum katlama ağacı bulmayı garanti eder, ancak verimliliği grafiğin yapısına bağlıdır. Kruskal'ın kenarlara odaklanması daha basit, ancak Prim'in öncelikli bir kuyruk kullanarak yoğun grafiklerle daha verimli olabileceği görülür.

  • Kruskal'ın dünya çapındaki çeşitli kenarları
  • Prim’s, bir başlangıçtan ağaca büyür
  • Her ikisi de verimlilik için farklı veri yapıları kullanırlar
  • Seçenekler grafik yoğunluğu ve büyüklüğüne bağlıdır