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.
Bu algoritmayı bir örnek ile anlatmak istersek:
* Orijinal graf aşağıdaki gibi olsun:
* İlk olarak düğüm noktaları arasındaki uzaklıkları gösteren bir matris hazırlanır. Eğer iki graf arasında bağlantı, yol yoksa buraya bir M değeri girilir. Bu değer çok büyük bir tam sayıyı temsil etmektedir. Algoritma uygulanırken bu değerler dikkate alınmaz. Yukarıdaki graf için bu matris aşağıdaki gibidir:
* Bu işlemden sonra başlamak için herhangi bir düğüm seçilir ve bu düğümün olduğu sütun silinir. Seçilen düğümün satırındaki en küçük sayı seçilerek işaretlenir. Bir sonraki adımın başlangıç düğümü, seçilen sayının ait olduğu sütun olacaktır.
* Yukarıdaki işlem sonucu en küçük eleman 5 olarak belirlendi. Şimdi 5'in bulunduğu sütun olan D seçilmiş oluyor. Bu sütun silinir ve eski satır (yani ilk seçmiş olduğumuz A'nın bulunduğu satır) ile D satırında en küçük eleman aranır:
* Aynı işlemler F için tekrar edilir:
* Aynı işlemler bu sefer C için uygulanır:
_______________________________________________________________________
Kaynaklar:
http://tr.wikipedia.org/wiki/Prim_algoritmas%C4%B1
http://www.ce.yildiz.edu.tr/mygetfile.php?id=1373
_______________________________________________________________________
Hiç yorum yok :
Yorum Gönder