Kruskal Algoritması

Kruskal algoritması, bir grafiği girdi olarak alan ve bu grafiğin kenarlarının alt kümesini bulan bir minimum yayılan ağaç algoritmasıdır. Her tepe noktasını içeren bir ağaç oluşturulur ve bu ağaç, girdi olarak alınan grafikten oluşturulabilecek tüm ağaçlar arasında minimum ağırlık toplamına sahiptir.

Kruskal Algoritması Çalışma Mantığı

Kruskal algoritmasında en düşük ağırlığa sahip kenarlardan başlanır ve hedefe ulaşana kadar kenar eklemeye devam edilir. Sırasıyla şu adımlar uygulanır:

1. Tüm kenarlar düşük ağırlıktan yükseğe doğru sıralanır.

2. En düşük ağırlığa sahip kenar alınır ve yayılan ağaca eklenir. Kenarın eklenmesi bir döngü yaratıyorsa, bu kenar reddedilir.

3. Tüm köşelere ulaşana kadar kenar eklenmeye devam edilir.

Kruskal Algoritması Örneği

1- Ağırlıklı bir grafik (graph) oluşturulur.

2- En az ağırlığa sahip kenar seçilir, 1'den fazla varsa herhangi biri seçilir.

3- Bir sonraki en kısa kenar seçilir ve eklenir.

4- Döngü oluşturmayan bir sonraki en kısa kenar seçilir ve eklenir.

5- Döngü oluşturmayan bir sonraki en kısa kenar seçilir ve eklenir.

6- Yayılan bir ağaç oluşana kadar tüm adımlar tekrarlanır.

Kruskal Algoritması Pseudocode

Kruskal Algoritmasının Java ile Açıklanması