Görsel konu anlatımı:
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.
2,288 views


Ç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