Prim Algoritması | Ağırlıklandırılmış Bağlı Bir Çizge Üzerinde Minimum Örten Ağaç Minimum Spanning Tree Bulan Algoritmalardan Birisi

Prim Algoritması

Prim Algoritması ağırlıklandırılmış ve bağlı bir çizge üzerinde minimum örten ağaçminimum spanning tree bulan algoritmalardan birisidir.

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:

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 oyle ki u B’nin elemanı olsun ve v N\B ‘nin elemanı olsun
T <- T U {e}
B <- B U {v}
endwhile
return T

Örnek

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.

Ä°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.

Seçilecek bir sonraki düğüm D veya A‘ya en yakın olanı. B 9 uzakta (D den), E 15, ve FF düğümünü ve DF ayrıtını iÅŸaretliyoruz. 6. En yakın 6 o yüzden

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.

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ı.

Burada sadece C ve G düğümlerini inceleyebiliriz. C, E‘den 5 uzakta ve G ise 9 uzakta. C‘yi ve EC ayrıtını seçiyoruz. Ayrıca BC‘yi de kırmızı olarak iÅŸaretliyoruz.

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. Toplan ağırlığı ise burada 39 oldu.

Kaynak: Kadim Dostlar ™ Forum

Bu içerik 29.05.2009 tarihinde Hale tarafından, Matematik ve Geometri Konu Anlatımları bölümünde paylaşılmıştır ve 911 kez okunmuştur. Bu içeriğin devamında incelemek isteyebileceğiniz 0 adet mesaj daha bulunmaktadır.

Prim Algoritması | Ağırlıklandırılmış Bağlı Bir Çizge Üzerinde Minimum Örten Ağaç Minimum Spanning Tree Bulan Algoritmalardan Birisi orjinal içeriğine ulaşmak için tıklayın ...