Prim Algoritmasi

Prim Algoritmasi

agirliklandirilmis ve bagli bir çizge üzerinde minimum örten agaçminimum spanning tree) bulan algoritmalardan birisidir. Ayritlarin bir alt kümesini, tüm dügümleri kapsayacak ve ayritlarin toplam agirligini (minimum yapacak sekilde bulur. Bagli olmayan bie çizgeye uygulandiginda sonucu bagli bilesenlerden yalniz birisi için bulur. Bu algoritma 1930 yilinda matematikçi Vojtech Jarnik tarafindan bulunmustur. Daha sonra bagimsiz olarak 1957'de bilgisayar bilimcisi Robert C. Prim ve 1959'da Dijkstra tarafindan tekrar bulunmustur. Bu nedenle bu algoritmaya DJP veya Jarnik algoritmasi da denir.

Sözdekod'u asagidaki gibi verilebilir:

function Prim(çizge N)
T : kapsayan agaç
B : eklenmis dügümler
B <- rastgele bir dügüm
while B<>N do
e = (u,v) seklinde en hafif ayriti bul oyle ki u B'nin elemani olsun ve v N\B 'nin elemani olsun
T <- T U {e}
B <- B U {v}
endwhile
return T

Örnek



http://img72.imageshack.us/img72/677...thm0svgwg3.png

Bu çizgenin orijinal hali. Ayritlarin üzerindeki sayilar agirliklari. Ayritlardan hiç biri henüz seçili degil ve D dügümü baslangiç dügümü olarak rastgele seçildi.



http://img72.imageshack.us/img72/419...thm1svghr5.png

Ikinci olarak seçilecek dügüm D'ye en yakin olani. A 5 , B 9, E 15, ve F 6 uzaklikta. Bunlardan en küçügü 5 dolayisiyla A dügümünü ve DA ayritini isaretliyoruz.



http://img72.imageshack.us/img72/430...thm2svguk4.png

Seçilecek bir sonraki dügüm D veya A'ya en yakin olani. B 9 uzakta (D den), E 15, ve FF dügümünü ve DF ayritini isaretliyoruz.
6. En yakin 6 o yüzden


http://img72.imageshack.us/img72/854...thm3svgre0.png

Algoritma ayni sekilde devam ediyor. B dügümü A'dan 7 uzakta ve isaretli. Burada DB ayriti kirmizi olarak isaretlendi çünkü daha önce hem B hem de D dügümleri isaretlenmisti. Bu yüzden bu ayrit kullanilamaz.



http://img72.imageshack.us/img72/581...thm4svgnb8.png

Bu durumda C, E ve G'den birini seçebiliriz. C, B'den 8 uzakta, E, B'den 7 uzakta ve G, F'den 11 uzakta. En yakin E oldugu için onu ve EB ayritini isaretliyoruz. Diger iki ayrit kirmizi çünkü onlari baglayan dügümler kullanildi.



http://img72.imageshack.us/img72/671...thm5svgtv0.png

Burada sadece C ve G dügümlerini inceleyebiliriz. C, E'den 5 uzakta ve G ise 9 uzakta. C'yi ve EC ayritini seçiyoruz. Ayrica BC'yi de kirmizi olarak isaretliyoruz.



http://img72.imageshack.us/img72/732...thm6svgoc5.png

G dügümü kalan son dügüm. F'den 11 uzakta ve E'den 9 uzakta. Bu nedenle E'yi ve EG'yi isaretliyoruz. Tüm dügümleri ekledigimize göre en hafif kapsayan agaç yesil olarak gözüküyor. Toplan agirligi ise burada 39 oldu.