Prim algoritması
Bu madde hiçbir kaynak içermemektedir. (Aralık 2020) (Bu şablonun nasıl ve ne zaman kaldırılması gerektiğini öğrenin)
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özdekodDeğiştir
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 bir ç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
ÖrnekDeğiştir
KaynakçaDeğiştir
- Ingilizce Wikepedia "Prim's algorithm" maddesi 24 Ekim 2021 tarihinde Wayback Machine sitesinde arşivlendi. (İngilizce)
Ayrıca bakınızDeğiştir
- Minimum örten ağaç problemi
Dış bağlantılarDeğiştir
|Wikimedia Commons'ta Prim algoritması ile ilgili ortam dosyaları bulunmaktadır.|
- Prim algoritması için animasyonlu çözüm 6 Eylül 2011 tarihinde Wayback Machine sitesinde arşivlendi.
- Prim Algoritmasi icin Java Apple)
- Pythom programi kullanarak "Minimum örten ağaç" problemi gosterimi, Ronald L. Rivest 9 Ağustos 2011 tarihinde Wayback Machine sitesinde arşivlendi.
- Prim Algoritmasi uygulanmasi icin Open Source Java Grafik paketi 31 Temmuz 2011 tarihinde Wayback Machine sitesinde arşivlendi.