Kruskal Algoritması Nedir?
Kruskal Algoritması, bir grafiğin tüm köşelerini birbirine bağlayan ve toplam kenar ağırlığı en az olan bir alt küme olan minimum yay ağacını (MST) bulmak için kullanılan popüler bir açgözlü algoritmadır. Özellikle ağ oluşturma ve rota planlama problemlerinde etkilidir.
Kruskal Algoritması, kenarları artan ağırlık sırasına göre sıralayarak ve döngü oluşturmayan kenarları minimum yay ağacına ekleyerek çalışır.
Adım adım çözümlü örnekler
Aşağıdaki grafiğin minimum yay ağacını Kruskal algoritması ile bulunuz.
1. Kenarları ağırlıklarına göre sıralayın: (A,B,1), (C,D,2), (B,C,3), (A,D,4), (B,D,5). 2. En hafif kenarı (A,B) ekleyin. 3. Bir sonraki en hafif kenarı (C,D) ekleyin. 4. Bir sonraki en hafif kenarı (B,C) ekleyin. Bu kenar bir döngü oluşturmaz. 5. Bir sonraki en hafif kenarı (A,D) eklemeye çalışın, ancak bu bir döngü oluşturur, bu yüzden atlayın. 6. Sonuç MST: {(A,B,1), (C,D,2), (B,C,3)}.Daha karmaşık bir grafikte Kruskal algoritmasının uygulanmasını gösteriniz.
1. Tüm kenarları ağırlıklarına göre küçükten büyüğe sıralayın. 2. Sıralı listeden ilk kenarı alın ve eğer bu kenar mevcut bileşenlerde bir döngü oluşturmuyorsa, MST'ye ekleyin. 3. Bu işlemi, MST'de V-1 kenar olana kadar tekrarlayın (V, köşe sayısıdır).
Bilgi kartları
Mini test
S1.Kruskal Algoritması'nın zaman karmaşıklığı genellikle nedir?
S2.Kruskal Algoritması'nda bir kenarın eklenip eklenmeyeceğine karar verirken en önemli kontrol nedir?
S3.Minimum yay ağacında kaç kenar bulunur?
Sık yapılan hatalar
Kruskal algoritması kenarları rastgele seçer. — Doğrusu: Kruskal algoritması kenarları artan ağırlık sırasına göre seçer.
Kruskal algoritması her zaman en kısa yolu bulur. — Doğrusu: Kruskal algoritması minimum yay ağacını bulur, tekil en kısa yolları değil.
Sıkça sorulan sorular
Kruskal Algoritması, Prim Algoritması'ndan nasıl farklıdır?
Prim Algoritması, bir köşe kümesinden başlayıp büyüyerek MST'yi oluştururken, Kruskal Algoritması tüm kenarları sıralar ve döngü oluşturmayanları ekleyerek ilerler.
Kruskal Algoritması hangi durumlarda daha etkilidir?
Grafik seyrek olduğunda (kenar sayısı köşe sayısının logaritmik katı civarında olduğunda) genellikle daha etkilidir.
Döngü tespiti için ayrık kümeler (DSU) yapısı neden önemlidir?
DSU, bir kenarın iki ucunun zaten aynı bağlantılı bileşende olup olmadığını hızlıca kontrol etmeyi sağlar. Bu, döngü oluşumunu verimli bir şekilde engeller.