Görsel konu anlatımı:

https://www.youtube.com/watch?v=k4e98XN6cPU

Yazan : Şadi Evren ŞEKER

Bir asgari tarama ağacı (minimum spanning tree) algoritması olan Dijkstra algoritması, işaretlemiş olduğu komşuluklara en yakın düğümü bünyesine katarak ilerler. Buna göre aşağıdaki grafiğin asgari tarama ağacını çıkaralım:

asgari tarama ağacı için örnek grafik

Yukarıdaki grafikte her düğüm için bir temsili harf ve her bağlantı için bir ağırlık değeri atanmıştır. Buna göre her düğümden diğerine gitmenin maliyeti belirlenmiştir.

Kruskal algoritmasında bütün yollar listelenip küçükten büyüğe doğru sıralanır. Bu liste yukarıdaki grafik için aşağıda verilmiştir:

x-v:1
w-v:1
w-u:1
x-w:2
u-s:2
x-y:3
t-u:3
u-v:3
y-v:4
s-t:4
y-z:5
y-t:5
z-t:10

Yukarıdaki liste çıkarıldıktan sonra sırasıyla en küçükten en büyüğe doğru komşuluklar işaretlenir. Bu işaretleme sırasında ada grupları ve grupların birbiri ile ilişkisine dikkat edilir. Yani şayet listedeki iki düğüm harfi de aynı adadan ise bu bağlantı atlanır. Aşağıda sırasıyla bu grafikteki adaların oluşması ve asgari tarama ağacının çıkarılması gösterilmiştir:
x-v:1
asgari_tarama_agaci_kruskal1.jpg
w-v:1
asgari_tarama_agaci_kruskal2.jpg
w-u:1
asgari_tarama_agaci_kruskal3.jpg
x-w bağlantısı atlanır, çünkü iki düğüm de zaten dolaşılmıştır bunun yerine u-s:2 bağlantısına atlanır.
asgari_tarama_agaci_kruskal4.jpg
x-y:3
asgari_tarama_agaci_kruskal5.jpg
t-u:3
asgari_tarama_agaci_kruskal6.jpg
Bu noktadan sonra u-v:3 , y-v:4 , s-t:4 , y-z:5 bağlantılarındaki her iki düğümde aynı adada olduğu için atlanır ve y-t:5 bağlantısına geçilir.
asgari_tarama_agaci_kruskal7.jpg
z-t:10 bağlantısı ise iki düğüm de gezildiği için yine gereksizdir.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Hayır gerekmez. Bakın mst (minimum spanning tree, asgari tarama ağacı) adı üzerinde bir ağaçtır.

    Ağaçlar tanım itibariyle, dairesel olmaz (acyclic graph). Bahsettiğiniz bağlantının alınması durumunda bir döngü (cycle) oluşmuş olur ki bu, tanımla çelişir.

    Ayrıca MST algoritmalarının amacı, bütün düğümleri (node) dolaşan en kısa yolu bulmaktır ve yukarıdaki son şekilde görülen yol zaten bütün düğümleri dolaşır. Bahsettiğiniz şekilde bir kenar (edge) daha çözüme eklenirse zaten ulaşabildiğimiz bir düğüm için fazladan yolu uzatmış oluruz.

  2. haktan aydın

    peki burada graph işaretlendiğinde ayrık olmayacak şekilde ayarlanmış normalde de ayrık olmaması gerekiyor değilmi

  3. Şadi Evren ŞEKER Article Author

    evet, mst (minimum spanning tree, asgari tarama ağacı) yapı olarak bağlı bir şekildir (connected graph) dolayısıyla bağlı şekiller üzerinde çalışır. Şayet üzerinde çalıştığınız şekil ayrık ise (unconnected) bu durumda MST bulamazsınız.

    MST tanım olarak bütün düğümleri dolaşan en kısa yoldur. Ayrık bir şekilde, bütün düğümleri dolaşan bir yol bulunamaz.

    başarılar

  4. Nilay

    Kruskal algoritması hakkında çok net bir bilgi edindim. çok teşekkür ederim. benim hiç anlamadığım bir diğer algoritma da gomory ve hu algoritması bu konuda da yardımcı olur musunuz?

  5. Şadi Evren ŞEKER Article Author

    gomory ve hu algoritması ile gomory-hu ağacını mı kastediyorsunuz? s-t cut algoritması? Sitede yayınlamamışım, listeye ekledim en kısa sürede bu konuda da bir yazı eklerim.

    başarılar

  6. Ömer

    Hocam kruskal veya primin maliyetsiz bir graf için(maliyetler 1) herhangi bir dilde kodu varsa paylaşabilirmisiniz.Bazı noktalarda hataya düşüyorum.Paylaşırsanız sevinirim.
    Teşekkürler.

  7. HAGI

    çok teşekkürler çok iyi bir anlatım emeginize saglık. Anlattığınız algoritmaları çok faydalı buldum.

  8. can

    Hocam video’da CD=1 , AC=1 , BE=2 ….. şeklinde kenarları düşük maliyet olacak şekilde sıraladıktan sonra sırayla düğümleri dolaşıyoruz ve eşit maliyette kenar sırası önemli değil diyoruz, fakat siz mesela CD=1 kenarından başlayarak Ziyaret listesi : CDAFBE şeklinde düzenlediniz, ben CD kenarından degilde AC kenarından başlasam ziyaret listesi farklı çıkıyor.

    Örnek : ACD… şeklide başlayıp ilerleyen bir ziyaret listesi çıkıyor. Ziyaret listesinin aynı çıkması lazım değilmi?

    İyi çalışmalar.

  9. Şadi Evren ŞEKER Article Author

    Evet Kruskal algortimasında farklı asgari tarama ağaçları (minimum spanning tree) elde edilebilir. Aslında tarama ağacı yegane (unique) olmak zorunda değildir. Önemli olan o şekilde (graph) en az maliyetle bütün düğümlerin (node) dolaşılmasıdır. Sonuçta bulduğunuz ağacın maliyeti videodaki ile aynıdır isterseniz maliyetleri toplayarak deneyebilirsiniz.

    Başarılar

  10. Nrdn

    Merhaba,

    Bizim elimizde bir corr matriksi var. Distance’a çevirtik ve öğelerimize kruskal algorithması uygulamak istiyoruz. Ama matrisimiz 74’e 74 olduğu için manuel yapması zor. Bu işlemleri yapmak için önerebileceğiniz bir program var mı acaba? Teşekkürler.

  11. Nrttn

    Hangi durumlarda Kruskal , Prims Algoritmasından daha avantajlıdır ? veya tam tersi Prims , hangi durumlarda Kruskal Algoritmasından daha avantajlıdır?

  12. Arda

    Öncelikle emeginize sağlık . Şurada bir takıldım :

    Bu noktadan sonra u-v:3 , y-v:4 , s-t:4 , y-z:5 bağlantılarındaki her iki düğümde aynı adada olduğu için atlanır ve y-t:5 bağlantısına geçilir.

    y-z :5 aynı değil,atlanması gereken kısım y-t :5 ve geçilmesi gereken yer y-z :5 olmayacak mı?

  13. gözde

    Hocam merhaba. kruskal algoritmasını c koduna çevirmeye çalışıyordum kenarların döngü oluşturup oluşturmadığını konrol nasıl edebilirim? Eğer sizde bu algoritmanın c kodu varsa paylaşırsanız çok sevinirim teşekkürler 🙂

  14. bilgisay

    Arda Bey,

    Doğru, yz bağlantısının alınıp yt’nin atlanması gerekiyor (hem y hem de t düğümleri daha önceden listemize eklenmiş bu yüzden y-t kenarı atlanarak y-z kenarının listeye eklenmesi gerekir) , en kısa sürede yazıda da düzeltmeye çalışacağım.

  15. elif

    Hocam kruskal algoritması nın prime göre avantajları nelerdir yani bu iki algoritmanın birbirlerine göre avantajları nelerdir bu konuda yardımcı olursanız çok sevinirim

  16. isim

    Yazının başında Bir asgari tarama ağacı (minimum spanning tree) algoritması olan “Dijkstra ” algoritması yazılmış. Dijkstra MST algoritması değil bildigim kadarıyla bir yanlışlık yapılmış :). Bu arada paylaşımlarınız için çok teşekkürler hocam.

  17. Mehmet

    “Bu noktadan sonra u-v:3 , y-v:4 , s-t:4 , y-z:5 bağlantılarındaki her iki düğümde aynı adada olduğu için atlanır ve y-t:5 bağlantısına geçilir.” açıklamasında y-z:5 ile y-t:5 in yerlerini değiştirmelisiniz. Hatalı olmuş..

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir