Prim Algoritması

Prim Algoritması, minimum spanning tree algoritmalarından biridir. Kenarların bir alt kümesini, tüm düğümleri kapsayacak ve kenarların toplam ağırlığını minimum yapacak şekilde bulur.

Bu algoritma 1930 yılında matematikçi Vojtech Jarnik tarafından bulunmuştur. Daha sonra bağımsız olarak 1957’de bilgisayar bilimcisi Robert C. Prim ve 1959’da Dijkstra tarafından tekrar bulunmuştur. Bu nedenle bu algoritmaya DJP veya Jarnik algoritması da denir.

Bir resim üzerinde anlatacak olursak.Resimdeki gibi grafımız olsun.Şimdi Z’den başlayalım.Y’ye 5 ve T’ye 10 birim. En küçük kenar Y olduğu için seçiyoruz..

asgari_tarama_agaci1

Şimdi Y ve Z deki kenarlardan en küçük olanı bulalım. Yden x’e 3 V’ye 4 ve T’ye 5 birim Z’den t ye 10 en küçük kenar X olduğundan x’i seçiyoruz seçiyoruz..

asgari_tarama_agaci_dijkstra1

asgari_tarama_agaci_dijkstra2

Şimdi ise Z Y ve Xteki Komşu kenarlardan en küçük olanına bakıyoruz.X’ten Vye 1 birim olduğunu görüyoruz. Hep aynı işlem. Amaç seçilen graflarda ki en küçük kenarı bulmak ..

asgari_tarama_agaci_dijkstra3

Yine aynı Taktik.V den bu sefer en küçük kenarı 1  olan  W’ye :)

 

asgari_tarama_agaci_dijkstra4 asgari_tarama_agaci_dijkstra5 asgari_tarama_agaci_dijkstra6asgari_tarama_agaci_dijkstra_cozum

En küçük kenarlar bunlarmış. Arada kalanlardan biri seçilirse bu prim algoritması olmaz. Kruskal alg. ile prim yöntemler farklı olsada sonuçlar her zaman tüm düğümleri kapsayacak ve kenarların toplam ağırlığını minimum yapar.

Not= Resimler http://bilgisayarkavramlari.sadievrenseker.com/2007/12/24/dijkstra-algoritmasi/ alınmıştır tabi 1 resim hatalı idi burada düzeltildi :)

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="">