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:
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
w-v:1
w-u:1
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.
x-y:3
t-u:3
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.
z-t:10 bağlantısı ise iki düğüm de gezildiği için yine gereksizdir.
Çok teşekkürler…
y-t 5 baglantısı da baglanması gerekmez mi ?
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.
peki burada graph işaretlendiğinde ayrık olmayacak şekilde ayarlanmış normalde de ayrık olmaması gerekiyor değilmi
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
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?
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
Algoritmanın anlatıldığı bir yazıyı yayınladım. Aşağıdaki bağlantıya tıklayarak ulaşabilirsiniz.
Gomory-Hu ağacı (gomory-hu tree)
başarılar
çok teşekkürler,karışık algoritma kavramlarından anlayamadığım bu konuyu burda çok iyi anladım
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.
Şadi bey gerçekten çok teşekkür ederiz.İnternete verdiğim para sizin gibiler sayesinde helalleşiyor.:)
Hocam chandy misra algorithmasıyla ilgilide bir makale yayınlayabilir misiniz acaba?
Hocam bu algorithmanın time ve message complexity’si nedir acaba ?
istediğiniz konu ile ilgili bir makaleyi aşağıdaki adreste yayınladım:
http://www.bilgisayarkavramlari.com/2012/01/22/filozoflarin-aksam-yemegi-dining-philosophers/
Başarılar
çok teşekkürler çok iyi bir anlatım emeginize saglık. Anlattığınız algoritmaları çok faydalı buldum.
Tesekkurler. cok achiklayici olmus!
Hocam meraba video da en son kısımda DE kenarını baglamayıp aynı adada demişsiniz fakat ayrı adada olmaları gerekmiyor mu ?
Teşekkürler
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.
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
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.
manuel ile neyi kast ediyorsunuz? Kruskal algoritması hemen her dilde kodu yazılabilen bir algoritmadır. Ancak matrisiniz çok büyük ve hafıza problemi yaşıyorsanız, dinamik programlama (dynamic programming) kullanabilirsiniz.
Hangi durumlarda Kruskal , Prims Algoritmasından daha avantajlıdır ? veya tam tersi Prims , hangi durumlarda Kruskal Algoritmasından daha avantajlıdır?
1 hafta sonra sınavım var yardımcı olabilecek yok mu ??
Ö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ı?
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 🙂
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.
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
Son aşamalarda y-t ve y-z karışmış sanırım. Yanlış anlaşılma olmasin
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.
evet en kısa yol algoritması (shortest path algorithm) olmalı, uyarınız için teşekkürler.
“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ş..
Hocam v-t : 8 bağlantısını hesaba katmamız gerekmez mi ?