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..
Ş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..
Ş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 ..
Yine aynı Taktik.V den bu sefer en küçük kenarı 1 olan W’ye 🙂
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 //bilgisayarkavramlari.sadievrenseker.com/2007/12/24/dijkstra-algoritmasi/ alınmıştır tabi 1 resim hatalı idi burada düzeltildi 🙂
