Prim Algoritması

Herkese merhabalar;

Bu yazımızda prim algoritmasında bahsedeceğiz.Bu algoritmada kruskal benzer şekilde çalışır.Bu sebeple bu yazıyı okumadan önce kruskal algoritmasını öğrenmiş olmanız sizin için daha avantajlıdır.

Algoritmayı Süzelim

Prims algoritması ağırlıklı ve yönsüz grafta(weighted undirected graph) asgari tarama ağacını(minimum spanning tree) bulan bir açgözlü algoritmadır(greedy algorithm).Normalde zaman karmaşıklığı(Time Complexity) O(V²) olan Prims algoritması minimum ikili yığın ağacı(minimum binary heap) veya öncelikli sıra(PriorityQueue) kullanılarak O(ElogV) , Fibonacci yığın ağacı(Fibonacci Heap) kullanılarak O(E+ VlogV) şeklinde optimize edilebiliyor.Özetle Prims algoritması bir graftaki düğümleri en az maliyetle dolaşmamızı sağlar.

Prim’s algoritmasını nerede kullanılır ?

Başlıca;

1. Ağ Tasarımı
2. Gezgin Satıcı Problemi (Travelling Salesman Problem)
3. Steiner tree Problemi
4. Cluster analizi ( k clustering problem)

Prim Algoritması Çalışma Mantığı

1. Graftaki rastgele bir vertexten başlanır.
   1. Başlangıç vertex in gidilen olarak işaretle
   2. Diğer vertexleri gidilecek olarak işaretle

Buradda iki adet küme tutcaz bir gidilen diğer gidecekler kümesi ilk başta gidilecek lerde olacak bütün vertexler

1. Gidilen nodelardan gidilmeyen nodelera ulaşan ve grafta cycle oluşturmayan min maliyetli kenarı bul

Şimdi iki adet küme var biri gidelen diğer gidilmeyen gidilen notalardan gidilmeyen node lara ulaşan ve cycle oluşturmayan min. Maliyetli kenarı alıcaz.

1. Min maliyetli kenarın gidilmeyen vertex in gidilen olarak işaretle
2. Bütün vertexler gidilen oluncaya kadar 2 ve 3. Adımları tekrarla.

Prim ve Kruskal algoritmasının karşılaştırılması ve karmaşıklığı

D.N:Bu konu ile ilgili daha detaylı anlattığım bir blog yazım bulunuyor.Ulaşmak için buraya tıklayınız

Algoritma karşılaştırmalarında hem zaman hemde hafıza kriteri vardır fakat girdi küçükse bu kriterler çok önemli değildir.Mesela n=10 için a ve b algoritmalarının zaman karşılığını düşünecek olursak.A algoritması 5000n b algoritması 2^n olsun

n=10 için a algoritması 50000 adımda b ise 8 adımda bitmektektedir.Bu durumda b avantajlı gibi gözüksede n büyüdükce örneğin n = 1000 için a 5 000 000 adımda b ise 2,5.10^41 adımda bitmektedir.

Özet

• A’dan B’ye varınca B’nin çıkışına bakmaktan ziyade A ve B’nin çıkışlarına bakmak gerekir.
• Prim grafı oluşturulurken vertexlerin cycle oluşturulmasına dikkat edilmelidir.
• Gidilen vertex’e tekrar gidilmez.
• Kruskal’da tüm kenarları bir kenara yaz küçükten büyüğe doğru sırala tarzında bir mantık vardı.Burada kenarları sıraladıktan sonra 2 gidilen node lu kenar varsa gidilmemeli çünkü cycle oluşturabilir.
• Kruskal’da bir kenarla,primde bir düğüm ile başlanır.
• Prim algoritması işaretlenmiş olan komşulara en yakın düğümü bünyesine katarak ilerler.
• Prim algoritması yayılarak gider,Kruskal ise kenarları ,kenarın konumu son adıma dayalı olmayacak şekilde ilerler.
• Prim’in algoritmasında, Kruskal’lar bağlantısız grafiklerde de çalışabilirken, grafik bağlantılı bir grafik olmalıdır.