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

Kruskal Algoritması Nedir? Kruskal Algoritması C Kodu

En kısa yol bulma algoritmalarından bir tanesi olan Kruskal algoritması bir graf yapısı içerisinde tarama ağacı oluşturarak tüm düğümlere ulaşmayı hedefler. Kağıt üzerinde uygularken oldukça efektif olan bu algoritma Prims algoritmasıyla aynı amacı taşır, ancak uygulama olarak düğümleri değil, kenarları inceler.

Prims Algoritması ile ilgili hazırladığımız derse hemen göz atın

Prims Algoritması Nedir?

Kruskal en kısa yol uygulamasında bir graf yapısındaki tüm kenarlar küçükten büyüğe sıralanır. Ve en küçük kenarlardan başlayarak ağacımızı oluşturmaya başlarız. Prims algoritmasında var olan kuralın aynısı bunda da vardır, cycle oluşmasına neden olan kenar tarama ağacına eklenmez. Cycle oluşması demek, kenarı çizdiğimizde kapalı bir alanın oluşmasına sebebiyet verilmesi demektir. Tabii buradaki temel kriter kapalı alandaki tüm düğümlerin ziyaret edilmiş olmasıdır.

Kruskal Algoritması Örnek

Prims algoritmasında kullandığımız örneğin aynısını kullanalım. İlk önce tüm kenarlar (düğümleriyle birlikte) maliyetlerine göre küçükten büyüğe sıralanır. (aşağıdaki resme göz atın)

Tüm düğümler ilk başta ziyaret edilmemiş olarak belirlenmiştir. biz seçtikçe ziyaret edildi olarak işaretliycez.

1. Adım:

 

İlk adımda ilk sıradaki H-G düğümünü ekleriz.

Ziyaret Edilmiş Olan Düğümler: H – G

2. Adım:

İkinci Adımda G-F kenarını ağacımıza ekleriz. G düğümü zaten ağacımızda olduğu için F düğümünü bağlarız.

Ziyaret Edilmiş Olan Düğümler: H – G – F

 

 

3. Adım:

Bu adımda üçüncü sıradaki kenarımız olan i-C kenarını ayrık bir biçimde ekleriz. Çünkü bu kenarın mevcut düğümlerle bağı (henüz) yok.

Ziyaret Edilmiş Olan Düğümler: H – G – F – İ – C

 

4. Adım:

Kenar listemize bakarsak bu adımda A – B kenarımız bulunuyor. Bu kenarı da ağacımıza ekleriz.

 

Ziyaret Edilmiş Olan Düğümler: H – G – F – İ – C – A – B

 

5. Adım

5. Sırada C-F kenarı bulunuyor. Riskliymiş gibi görünüyor ama cycle oluşturmuyor, bu yüzden C-F arasına kenarı eklememizde sorun yok.

 

6. Adım

6. Sırada İ-G kenarı var. bu kenarı eklemeyiz. Çünkü İ-G kenarını eklersek Cycle oluşturmuş oluruz. Eğer ekleseydik İ-G-F-C içinde Cycle oluşturmuş olacaktık ve yapımız ağaç niteliğini kaybedecekti. Bizim amacımız MST (mininmum spanning tree) oluşturmak olduğundan bu kenarı eklemeyiz.

 

7. Adım:

7. Sırada İ-H kenarı var, yine Cycle oluşturuyor, bu yüzden bu kenarı eklemeyiz.

 

8. Adım:

Bu adımda C-D kenarımız bulunuyor. (8. sıradaki kenar) C düğümümüz ekli ama D düğümü henüz eklenmemiş, bu yüzden gönül rahatlığıyla ekleriz.

9. Adım: 

Bu adımda B-C kenarımız bulunuyor. Her iki düğümde ziyaret edildiği için ekleme yaparken dikkatli olacağız. Baktığımızda Cycle oluşturmadığını görüyoruz. Bu yüzden ekleyebiliriz. B-C arasına kenarı ekliyoruz sadece.

10. Adım:

10. sırada A-H kenarı var. Ancak bu kenarı ekleyemeyiz. Tekrar Cycle oluşturmuş oluruz. Kontrol edelim A-H-G-F-C-B–A Cycle oluşturuyor.

Graf Üzerinde bir noktadan başlayıp aynı noktaya tekrar varabiliyorsak Cycle var demektir.

 

11. Adım

11. sırada D-E kenarı var. D düğümü ziyaret edilmiş ancak E henüz eklenmemiş. E düğümünü ekleyip kenarı birleştiriyoruz.

Gördüğünüz üzere tüm düğümleri ziyaret etmiş olduk. Diğer adımlarda her kenar Cycle oluşturacağı için eklenmeyecektir. yani hocanız sorarsa her kenar için adım yazmayı ihmal etmeyin. İş burada bitti sonuç olarak.

 

Kruskal Algoritması C Kodu


#include<stdio.h>
 
#define MAX 30

//Kenarları tutan yapımız
// u source, v destination ve w ağırlık/maliyet
// Buradaki u ve v düğümleri temsil edecek.
typedef struct edge
{
    int u,v,w;
}edge;

//kenar listesi tutan yapımız 
typedef struct edgelist
{
    edge data[MAX];
    int n;
}edgelist;
 
edgelist elist;

//Komşuluk matrisi
int G[MAX][MAX],n;
edgelist spanlist;
 
//Temel fonksiyon tanımlamaları
void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();
 
void main()
{
    int i,j,total_cost;
    
    printf("\nDugum sayisini giriniz... :");
    
    scanf("%d",&n);
    
    printf("\nKomsuluk Matrisini girin:\n");
    
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&G[i][j]);
            
    kruskal();
    print();
}
 
void kruskal()
{
    int belongs[MAX],i,j,cno1,cno2;
    elist.n=0;
 
    //Aşağıdaki döngü source, destination düğümleri ile düğümler arasındaki maliyeti değişkenlere aktarıyor
    for(i=1;i<n;i++)
        for(j=0;j<i;j++)
        {
            if(G[i][j]!=0)
            {
                elist.data[elist.n].u=i;
                elist.data[elist.n].v=j;
                elist.data[elist.n].w=G[i][j];
                elist.n++;
            }
        }
 
    //Kenarları küçükten büyüğe sıralayan fonksiyonu çağırıyoruz.
    sort();
    
    //Düğümlerin Parentlarını oluşturuyor.
    for(i=0;i<n;i++)
        belongs[i]=i;
    
    spanlist.n=0;
    
    for(i=0;i<elist.n;i++)
    {
        cno1=find(belongs,elist.data[i].u);
        cno2=find(belongs,elist.data[i].v);
        
        if(cno1!=cno2)
        {
            spanlist.data[spanlist.n]=elist.data[i];
            spanlist.n=spanlist.n+1;
            union1(belongs,cno1,cno2);
        }
    }
}
 
int find(int belongs[],int vertexno)
{
    return(belongs[vertexno]);
}
 
void union1(int belongs[],int c1,int c2)
{
    int i;
    
    for(i=0;i<n;i++)
        if(belongs[i]==c2)
            belongs[i]=c1;
}
 
void sort()
{
    int i,j;
    edge temp;
    
    for(i=1;i<elist.n;i++)
        for(j=0;j<elist.n-1;j++)
            if(elist.data[j].w>elist.data[j+1].w)
            {
                temp=elist.data[j];
                elist.data[j]=elist.data[j+1];
                elist.data[j+1]=temp;
            }
}
 
void print()
{
    int i,cost=0;
    
    for(i=0;i<spanlist.n;i++)
    {
        printf("\n%d\t%d\t%d",spanlist.data[i].u,spanlist.data[i].v,spanlist.data[i].w);
        cost=cost+spanlist.data[i].w;
    }
 
    printf("\n\nAsgari Tarama Agacinin Maliyeti=%d",cost);
}

Bir cevap yazın

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