Prim Algoritması Nedir?

**Prof. Dr. Sinsi** · 12-19-2012

Prim Algoritması
MsXLabs

org & Vikipedi, özgür ansiklopedi

Prim Algoritması, ağırlıklandırılmış ve bağlı bir çizge üzerinde minimum örten ağaç (minimum spanning tree) problemine çözüm bulma algoritmalardan birisidir

Çözüm ve sözdekod
Ayrıtların bir alt kümesini, tüm düğümleri kapsayacak ve ayrıtların toplam ağırlığını minimum yapacak şekilde bulur

Bağlı olmayan bie çizgeye uygulandığında sonucu bağlı bileşenlerden yalnız birisi için 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

Sözdekod'u aşağıdaki gibi verilebilir:

HTML Kodu:

function Prim (çizge N) T: kapsayan ağaç B: eklenmiş düğümler B <- rastgele bir düğüm while B<>N do e = (u,v) şeklinde en hafif ayrıtı bul öyle ki u B'nin elemanı olsun ve v NB 'nin elemanı olsun T <- T U {e} B <- B U {v} endwhile return T

Örnek
200px-Prim_Algorithm_0

svg

png

Bu çizgenin orijinal hali

Ayrıtların üzerindeki sayılar ağırlıkları

Ayrıtlardan hiç biri henüz seçili değil ve D düğümü başlangıç düğümü olarak rastgele seçildi

200px-Prim_Algorithm_1

svg

png

İkinci olarak seçilecek düğüm D'ye en yakın olanı

A 5 , B 9, E 15 ve F 6 uzaklıkta

Bunlardan en küçüğü 5 dolayısıyla A düğümünü ve DA ayrıtını işaretliyoruz

200px-Prim_Algorithm_2

svg

png

Seçilecek bir sonraki düğüm D veya A'ya en yakın olanı

B 9 uzakta (D'den), E 15, ve F 6

En yakın 6, o yüzden F düğümünü ve DF ayrıtını işaretliyoruz

200px-Prim_Algorithm_3

svg

png

Algoritma aynı şekilde devam ediyor

B düğümü A'dan 7 uzakta ve işaretli

Burada DB ayrıtı kırmızı olarak işaretlendi

Çünkü daha önce hem B hem de D düğümleri işaretlenmişti

Bu yüzden bu ayrıt kullanılamaz

200px-Prim_Algorithm_4

svg

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 yakın E olduğu için onu ve EB ayrıtını işaretliyoruz

Diğer iki ayrıt kırmızı çünkü onları bağlayan düğümler kullanıldı

200px-Prim_Algorithm_5

svg

png

Burada sadece C ve G düğümlerini inceleyebiliriz

C, E'den 5 uzakta ve G ise 9 uzakta

C'yi ve ECayrıtını seçiyoruz

Ayrıca BC'yi de kırmızı olarak işaretliyoruz

[size="3">[color="]
G düğümü kalan son düğüm

F'den 11 uzakta ve E'den 9 uzakta

Bu nedenle E'yi ve EG'yi işaretliyoruz

Tüm düğümleri eklediğimize göre en hafif kapsayan ağaç yeşil olarak gözüküyor

Toplam ağırlığı ise burada 39 oldu

[/size]

12-19-2012	#1
Prof. Dr. Sinsi	Prim Algoritması Nedir? Prim Algoritması MsXLabsorg & Vikipedi, özgür ansiklopedi Prim Algoritması, ağırlıklandırılmış ve bağlı bir çizge üzerinde minimum örten ağaç (minimum spanning tree) problemine çözüm bulma algoritmalardan birisidir Çözüm ve sözdekod Ayrıtların bir alt kümesini, tüm düğümleri kapsayacak ve ayrıtların toplam ağırlığını minimum yapacak şekilde bulur Bağlı olmayan bie çizgeye uygulandığında sonucu bağlı bileşenlerden yalnız birisi için 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 Sözdekod'u aşağıdaki gibi verilebilir: HTML Kodu: function Prim (çizge N) T: kapsayan ağaç B: eklenmiş düğümler B <- rastgele bir düğüm while B<>N do e = (u,v) şeklinde en hafif ayrıtı bul öyle ki u B'nin elemanı olsun ve v NB 'nin elemanı olsun T <- T U {e} B <- B U {v} endwhile return T Örnek 200px-Prim_Algorithm_0svgpng Bu çizgenin orijinal hali Ayrıtların üzerindeki sayılar ağırlıkları Ayrıtlardan hiç biri henüz seçili değil ve D düğümü başlangıç düğümü olarak rastgele seçildi 200px-Prim_Algorithm_1svgpng İkinci olarak seçilecek düğüm D'ye en yakın olanı A 5 , B 9, E 15 ve F 6 uzaklıkta Bunlardan en küçüğü 5 dolayısıyla A düğümünü ve DA ayrıtını işaretliyoruz 200px-Prim_Algorithm_2svgpng Seçilecek bir sonraki düğüm D veya A'ya en yakın olanı B 9 uzakta (D'den), E 15, ve F 6 En yakın 6, o yüzden F düğümünü ve DF ayrıtını işaretliyoruz 200px-Prim_Algorithm_3svgpng Algoritma aynı şekilde devam ediyor B düğümü A'dan 7 uzakta ve işaretli Burada DB ayrıtı kırmızı olarak işaretlendi Çünkü daha önce hem B hem de D düğümleri işaretlenmişti Bu yüzden bu ayrıt kullanılamaz 200px-Prim_Algorithm_4svgpng 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 yakın E olduğu için onu ve EB ayrıtını işaretliyoruz Diğer iki ayrıt kırmızı çünkü onları bağlayan düğümler kullanıldı 200px-Prim_Algorithm_5svgpng Burada sadece C ve G düğümlerini inceleyebiliriz C, E'den 5 uzakta ve G ise 9 uzakta C'yi ve ECayrıtını seçiyoruz Ayrıca BC'yi de kırmızı olarak işaretliyoruz [size="3">[color="] G düğümü kalan son düğüm F'den 11 uzakta ve E'den 9 uzakta Bu nedenle E'yi ve EG'yi işaretliyoruz Tüm düğümleri eklediğimize göre en hafif kapsayan ağaç yeşil olarak gözüküyor Toplam ağırlığı ise burada 39 oldu[/size]