Home / Algoritmalar / Prims Algoritması Nedir? Prims Algoritması C Kodu

Prims Algoritması Nedir? Prims Algoritması C Kodu

En Kısa yol bulma algoritmalarından olan Prims algoritması Greedy bir algoritmadır. Öncelikli olarak En kısa yol bulma algoritmalarındaki temel amacı belirtelim. En Kısa yol bulma algoritmalarında ağırlıklı graf kullanılır. İki düğüm arası bir maliyet değeri vardır. Bunu iki şehir arasındaki uzaklık gibi düşünebilirsiniz. Bu tip algoritmalardaki amaç iki düğüm arasındaki en kısa yolu bulma olduğu gibi, tüm düğümleri en kısa yolu kullanarak gezmeyi hedeflemek de olabilir. Prims Algoritmasındaki amaç tüm düğümleri en az maliyet ile dolaşmaktır.

Prims Algoritması Nedir?

İçerik

Prims Algoritmaları Hem Graflar hem de ağaçlar üzerinde uygulanabilir. Amacı Sistem içerisindeki tüm düğümleri en az maliyetle dolaşmaktır. İlk olarak ağaçlara yönelik oluşturulmuştur. Zaten algoritmanın çalışma mantığı Asgari tarama ağacı (MST-Minimum Spanning Tree) oluşturarak tüm düğümleri gezmektir. Yani kaç tane düğümümüz olursa olsun, Prims algoritmasının hedefi o graf yapısı içerisinde bir tarama ağacı oluşturarak tüm düğümlere varmayı hedefler. Gerçek hayatta network yapılarında ve benzeri veri içeren birimlerde sıkça kullanılır. Bu algoritmanın kardeşi Kruskal Algoritmasıdır. Bu algoritmadan da bir sonraki yazımızda bahsedeceğiz.

MST – Minimum Spanning Tree Nedir?

Prims ve Kruskal algoritmalarında sıkça duyacağımız bu kavramı anlamamız algoritmayı yorumlamamızda oldukça önemlidir. MST, Türkçesi Asgari Tarama Ağacı olarak da söylenmektedir, tüm düğümleri en az maliyetle gezmeyi hedefler. Kruskal ve Prim’s algoritmasında bu sistemin uygulanışı farklıdır. Biz bu yazımızda Primsten bahsediyor olacağız. MST’de temel hedef, iki düğümü Cycle oluşturmadan birleştirmektir. Cycle oluşturmak Ağaç durumunu bozar, bu yüzden cycle oluşumunun önüne geçmek gerekir.

Peki biz Cycle oluşup oluşmadığını nasıl anlayacağız? Çok basit, iki düğüm arasını birleştirdiğimizde içeride ziyaret edilmiş düğümlerden oluşan bir kapalı alan oluşuyorsa bu cycle oluşturmuş demektir.

 

Prims Algoritması Örnek

Örnek olarak yukarıdaki graf yapısını kullanalım. Bu yapıyı Youtube’daki bir video’dan buldum örnek hoşuma gittiği için kullanıyorum. A düğümünden Başlıycaz ve adım adım ilerliycez.

1. Adım:

A Düğümünden En az Maliyetle Gidilebilen düğüm işaretlenir ve burası bizim yapımız olur.

Gördüğünüz üzere A’ya en yakın düğüm B idi, Biz bu iki düğümü ziyaret edildi olarak işaretledik. Üstelik bu iki düğüm artık bizim yapımızı oluşturdu. Bundan sonraki adımda en yakın yolu ararken bu iki düğümü referans alacağız.

Düzeltme: Yukarıdaki iki resimde alt sırada bulunan B düğümü aslında H düğümü olacak. Bundan sonraki adımlarda o hata bulunmuyor.

Ziyaret Edilen Düğümler: A – B

 

2. Adım:

Biz artık en kısa yolu ararken hem A düğümünden hem de B Düğümünden olanlara bakacağız. Şimdi uzaklıkları kontrol edelim.

A – H : 8

B – H : 11

B – C: 8

iki tane 8 var, istediğimizi seçeriz. Biz bu örnekte B-C arasını seçiyoruz.

Artık C de ziyaret edilen düğümler arasında. Yeni ağacımız A – B – C düğümlerinden oluşuyor. Yani en kısa yol ararken artık bu üç düğümden çıkışlara bakacağız.

 

3. Adım:

A – B – C sisteminden çıkan en kısa yollara bakalım. C – i arasının en kısa olduğunu göreceksiniz. C – i arası da ağacımıza katıyoruz.

Artık yeni sistemimiz (Asgari Tarama Ağacımız) A – B -C – İ düğümlerinden oluşuyor. (Tüm bu düğümleri ziyaret edilmiş olarak işaretlediğimize dikkat edin.

 

4. Adım:

Tarama ağacımızdan tüm çıkışları tekrardan kontrol ediyoruz.

C – D : 8

C – F  : 4

i – G : 6

i – H : 7

Hepsini yazmıyorum, mantığı görün diye yazdım, zaten bakında C – F arasının en kısa kenar olduğunu görüyorsunuz.

Yeni Asgari Tarama Ağacımız A – B – C – İ – F oldu artık.

 

5. Adım:

Tüm Asgari Tarama ağacımızdan çıkışlara baktığımızda F – G : 2 aralığının en küçük olduğunu görüyoruz. Bu yüzden MST’ye G düğümünü de ekliyoruz.

Yeni Asgari Tarama Ağacımız A – B – C – İ – F – G  olarak güncelledik.

 

6. Adım:

Tüm çıkışları kontrol ettiğimizde G – H Aralığının 1 olduğunu görüyoruz. Bu yüzden H’yi de ağacımıza dahil ediyoruz.

Yeni Asgari Tarama Ağacımız A – B – C – İ – F – G – H olarak güncelledik.

 

 

7. Adım:

En güzel adıma geldik. Asgari tarama ağacımıza baktığınızda en kısa yolun G – İ arası olduğunu göreceksiniz. Ama burayı birleştiremeyiz. Zira birleştirirsek Cycle oluşturmuş oluruz.

Prims Algoritmasında MST oluştururken Cycle Oluşumuna sebebiyet veren kenar çizemezsiniz.

Yani en kısa yol G – İ : 6 olmasına rağmen biz bunu Cycle oluşturduğu için eklemiyoruz, bunun yerine diğer kısa kenar olan C – D : 7′ yi ekliyoruz. Amacımız ağaç oluşturmak, graf değil.

Yeni Asgari Tarama Ağacımız A – B – C – İ – F – G – H – D olarak güncelledik.

 

 

8. Adım:

Tüm ağaca baktımızda  en küçük D – E : 9 olduğunu göreceksiniz.

Aslında daha kısa yollar var ancak temel şartımız asla Cycle oluşturmamaktı.

Gördüğünüz üzere tüm düğümleri ziyaret ettik. Asgari tarama ağacımızı tamamlamış olduk. Burada ne yaptık? En kısa kulları kullanarak tüm düğümleri gezmeyi başardık. Gereksiz uzunluktaki yolları çıkardığımızda Asgari Tarama Ağacı aşağıdaki gibi olmaktadır.

 

Prims Algoritması C Kodu


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MELKOR 1000000

/*
Aşağıdaki matrisi kopyalayıp matris.txt dosyasına kaydedin. Bu bizim kullanacağımız veri yapısı olacak
Unutmayın, kodunuzla aynı klasörde olmalı.
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0
*/

//Matrisimizi tutacağımzı dizi
int Array[5][5];

//Matrisimizi matris.txt dosyasından okuyup dizimize aktaran fonksiyon
void readMatrix()
{
    int i = 0;
    FILE *fp = fopen("matris.txt", "r");

    while(fscanf(fp, "%d %d %d %d %d",
                 &Array[i][0],
                 &Array[i][1],
                 &Array[i][2],
                 &Array[i][3],
                 &Array[i][4]
                 ) != EOF)
    {
        i = i + 1 ;
    }
}

//En kısa yolun indisini geri döndüren yardımcı fonksiyon. Hocalar burayı sorarlar dikkat edin.
int minKey(int key[], bool visited[])
{
    int min = MELKOR;
    int minIndex, i;
    for( i = 0; i < 5; i++)
    {
        //Eğer bir düğüm ziyaret edilmemiş ve min değerinden daha küçükse burayı seçiyoruz.
        if(visited[i] == false && key[i] < min)
        {
            min = key[i];
            minIndex = i;
        }
    }
    //minIndex'i return ediyoruz.
    return minIndex;
}

//Esas fonksiyon burada, veri yapımızı tutan diziyi parametre olarak veriyoruz.
void prims(int Array[5][5])
{
    //Genel değişkenler
    int i, j, t;
    int key[5];
    int parent[5];
    bool visited[5];

    //Tüm düğümleri ziyaret edilmemiş olarak işaretleyip, maliyeti sonsuz yapıyoruz.
    for(i = 0; i < 5; i++)
    {
        visited[i] = false;
        key[i] = MELKOR;
    }

    //Başlangıç düğümünü belirliyoruz. Maliyeti sıfır olur başlangıç düğümünün. Parentı olmadığı için -1 veriyoruz.
    key[0] = 0;
    parent[0] = -1;

    //5 düğümümüz olduğu için dış döngümüz 5 defa dönecek
    for(j = 0; j < 5; j++)
    {
        //En kısa yolu u değerine atıyoruz
        int u = minKey(key, visited);
        //Ziyaret edildi olarak işaretliyoruz.
        visited[u] = true;

        //Fonksiyonun can damarı
        for(t = 0; t < 5; t++)
        {
            //Asgari tarama ağacına en az maliyete sahip ziyaret edilmemiş düğümü ekliyoruz. Ancak Parent'ı tutmayı unutmuyoruz.
            if(Array[u][t] && visited[t] == false && Array[u][t] < key[t])
            {
                key[t] = Array[u][t];
                parent[t] = u;
            }
        }
    }
    printMST(parent, Array);

}

//Asgari tarama ağacını yazdıran fonksiyon
int printMST(int parent[], int Array[5][5])
{
   int i;
   for (i = 1; i < 5; i++)
      printf("%d - %d    %d \n", parent[i], i, Array[i][parent[i]]);
}

int main()
{
    readMatrix();
    prims(Array);
}


2 comments

  1. Kod başka matrislerde saçmalıyor, lütfen kodunuzu güncelleyin.

    • algoritmauzmani

      Saçmaladığı duruma örnek verir misiniz? Değiştirdiğiniz matrise bağlı olarak ilgili değişkenleri değiştirdiğinizden de emin misiniz? Hata oluşan ya da yanlış sonuç veren matris örneğini yollarsanız durumu güncelleyebilirim.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir