Kruskal Algoritması

Bir asgari tarama ağacı (minumum spanning tree) algoritması olan Dijkstra algoritması, işaretlemiş olduğu komşuluklara en yakın düğümü bünyesine katarak ilerler.

Buna göre  kruskal nasıl yapılır ? Tüm kenarları en küçük kenardan başlayarak yazıyoruz.Ve en küçük kenarlardan başlıyoruz üstünü çize çize gidiyoruz..

Buna göre aşağıdaki grafiğin asgari tarama ağacını çıkaralım:

asgari_tarama_agaci1

X-V: 1

asgari_tarama_agaci_kruskal1

w-v:1

asgari_tarama_agaci_kruskal2

w-u:1

asgari_tarama_agaci_kruskal3

“x-w:2(Kullanılmaz. x ve w v ile birleşmiz. Arada kalan düğüm kullanılmaz.) ”

u-s:2

asgari_tarama_agaci_kruskal4

x-y:3

asgari_tarama_agaci_kruskal5

t-u:3

asgari_tarama_agaci_kruskal6

y-z:5

asgari_tarama_agaci_kruskal7

u-v:3
y-v:4
s-t:4  Neden x-w kullanmadıysak bunlarıda o yüzden kullanmadık. Arada kalan düğümler yani ağacımız bağlanmıycak tek bir ağaç olcak
y-t:5
z-t:10

“Farkettiniz mi? prim ile kruskal algoritması aynı çıktı. En kısa yolu buldu :)”

Post Author: umiitkose

Bir Cevap Yazın

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

Şu HTML etiketlerini ve özelliklerini kullanabilirsiniz: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">