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.


[...] tarama ağacını veren en meşhur algoritmalar: Kruskal Algoritması Prims Algoritması Dijkstra [...]
Ç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.