Makale Özeti

Kruskal algoritması bağlı düğümler içerisinde en kısa şekilde tüm düğümleri dolaşmayı sağlar (Minimum Spanning Tree Solving). Algoritma 1956 yılında Joseph Kruskal tarafından yazılmış hala çok yaygın olarak kullanılan bir algoritmadır. Ağ yapılarında, grafik çizimlerinde çok sıklıkla kullanılmaktadır. Algoritma en küçük yolları alıp bir döngü(loop) yapmadan tüm düğümleri dolaşarak, tüm düğümleri en kısa yoldan nasıl dolaşılabileceğini bulur. Tüm düğümlerin bağlı ve yolların çift yönlü tek ağırlıklı olması gerekmektedir yani A düğümünden B düğümüne gitmenin maliyeti x ise B düğümünden A düğümüne gitmenin de maliyetinin x olması gerekmektedir. Farklı ağırlıklı yapılarda Kruskal'dan farklı algoritmalar kullanılarak çözüm bulunur.

Makale

 

Giriş

Kruskal algoritması bağlı düğümler içerisinde en kısa şekilde tüm düğümleri dolaşmayı sağlar (Minimum Spanning Tree Solving). Algoritma 1956 yılında Joseph Kruskal tarafından yazılmış hala çok yaygın olarak kullanılan bir algoritmadır. Ağ yapılarında, grafik çizimlerinde çok sıklıkla kullanılmaktadır. Algoritma en küçük yolları alıp bir döngü(loop) yapmadan tüm düğümleri dolaşarak, tüm düğümleri en kısa yoldan nasıl dolaşılabileceğini bulur. Tüm düğümlerin bağlı ve yolların çift yönlü tek ağırlıklı olması gerekmektedir yani A düğümünden B düğümüne gitmenin maliyeti x ise B düğümünden A düğümüne gitmenin de maliyetinin x olması gerekmektedir. Farklı ağırlıklı yapılarda Kruskal'dan farklı algoritmalar kullanılarak çözüm bulunur.

Algoritmayı aşağıda oluşturduğumuz bir örneklem üzerinden açıklayacağım. Aşağıdaki L matrisi bağlı olan şehirlerin arasındaki uzaklığı bize göstersin. Aşağıdaki resimde bağlı olan düğümler gösterilmiştir.

Yukarıdaki şekilde herhangi bir düğümden başlayarak en az maliyetle tüm düğümleri dolaşmamız gerekmektedir. Yurakıdaki şeklin matris üzerinde aşağıdaki gibi gösterebiliriz. Bu matris düğümler arasındaki ağırlığı maliyeti gösterecektir. -1 olarak gösterilen ağırlıklar bu iki düğüm arasında yolun olmadığı anlamına gelmektedir.

 int[,] L ={
                    { -1,  5, 30, -1, -1, -1},
                    {  5, -1, 20, 10, -1, -1},
                    { 30, 20, -1, 10, 15, -1},
                    { -1, 10, 10, -1,  5, 20},
                    { -1, -1, 15,  5, -1, 15},
                    { -1, -1, -1, 20, 15, -1},
               };

Pseudocode

T = {}	// MST mizi tutacak

while (T'nin sahip olduğu n-1 tane kenar bulana ya da L matrisinde çekecek kenar bulunmayana kadar) {

     pick (u,v)    --> L den en küçük elemanı çek 

    delete (u,v)  --> L den çıkardığın kenar için L'ki ilişkiyi sil

    adding (u,v)  --> Alınan kenar çözümde döngü(loop) yapmıyorsa bunu T çözüm matrisine ekle

}

Algoritmada en önemli kısmı alınan kenarların döngüye(loop) neden olup olmadığıının kontrolüdür. Eğer herhangi bir şekilde döngü(loop) oluşursa bu bizim daha önce gittiğimiz bir düğüme yeniden gitmeye çalıştığımıza ve yeni bir maliyete sebep olacağını gösterir. Alınan kenarları ve birleştirilen düğümleri C matrisinde tuttuk. C matrisini kullanarak döngüye girilip girilmediğine bakacağız birleştirilen düğümleri 1 başlayarak artan sıralı olarak C matrisine yazacağız birleştirdiğimiz düğümlerin değerleri eşit olacak ve hangi düğümlerin birbiri ile bağlı olduğunu anlayabileceğiz. Algoritamanın adım adım çalışması aşağıda gösterilmiştir. 

C[]-> -1,-1,-1,-1,-1,-1

C[]->  1,  1,-1,-1,-1,-1

En az maliyetli yol bulunur A-B arası 5 bu çözüme

eklenir ve matris listesinden çıkarılır.

C matrisinde A ve B nin birleştiğini göstermek

için 0 ve 1 inci gözü pozitif yaparız 

(A-B = 5 çözüme eklenir.)

C[]->  1,  1,-1,-1,-1,-1

C[]->  1,  1,-1,  2, 2,-1

En küçük yol D ve E düğümleri arasında 5

olarak bulunur. C matrisinde 3 ve 4 üncü gözler

 2 yapılır ve birleştirilir.

(D-E = 5 çözüme eklenir.)

C[]->  1,  1,-1,  2, 2,-1 

C[]->  1,  1,-1,  1, 1,-1 

En az maliyetli yol B ve D düğümleri arasında 10

olarak bulunur. C matrisinde B ve D düğümlerini

birleştirmek gerekiyor. Bu birleştirme aslında B

ve D nin önceden birleştiği A ve E düğümlerini

de birleştirdiği için A B D E düğümlerini temsil

eden gözler aynı pozitif sayı olur. 

(B-D = 10 çözüme eklenir.)

C[]->  1,  1,-1,  1, 1,-1

C[]->  1,  1, 1,  1, 1,-1

En az maliyetli yol D ve C düğümleri arasında 10

olarak bulunur. C matrisinde 2 nci göz pozitif

olur. 

(D-C = 10 çözüme eklenir.)

C[]->  1,  1, 1,  1, 1,-1

 En az maliyetli yol C ve E düğümleri arasında 15

olarak bulunur. Fakat C matrisine baktığımızda

C matrisi icin 2 nci göz pozitif ve 1, E matrisi

için 4 üncü göz pozitif ve 1'dir. Bu iki düğümün

zaten bağlı olduğunu ve C-E yolu alınırsa

döngü(loop) olacağını (D-C-E) gösterir. C-E

yolunu çözüme almayız.

C[]->  1,  1, 1,  1, 1,-1

C[]->  1,  1, 1,  1, 1, 1 

En az maliyetli yok E ve F düğümleri arasında ve 15

olarak bulunur. F yi gösteren 5 inci göz

pozitif olur. Tüm düğümler dolaşıldığı için

( C matrisinde tüm düğümler pozitif ve aynı sayı

olduğu için) algoritma MST problemini çözmüş olur.

(E-F =15 çözüme eklenir.)

 

 

Diğer kenarlara bakılmasına gerek yoktur çünkü biz

kenarları dolaşırken küçük uzunlunlu kenarlardan

büyüğe doğru dolaştık. Yani daha kısa bir yol

olma imkanını bırakmadık.

Örnek Kod

    class Kruskal
    {
        private int rank = 0;
        private int[,] L;
        private int[] C;
        private int[,] tempL;
        private int row;
        private int column;
        public int[,] sol;
        private int connectedEdges;
        //getting minimal value of distance of between to the adjacent nodes
        //setting the positon of the distance(colunm,row)
        public int getMinimumDistance()
        {
            int temp = Int32.MaxValue;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++)
                {
                    if (tempL[i, j] > 0 && tempL[i, j]<temp)
                    {
                        temp = tempL[i, j];
                        row = i;
                        column = j;
                    }                    
               }
            }
            tempL[row, column] = tempL[column, row] = -1;
            return temp;
        }
        //construction of class, getting nodes distance array and its' rank
        public Kruskal(int paramRank, int[,] paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            tempL = new int[paramRank, paramRank];
            sol = new int[paramRank, paramRank];
            rank = paramRank;
            connectedEdges = 0;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++)
                {
                    L[i, j] = paramArray[i, j];
                    tempL[i, j] = paramArray[i, j];
                    sol[i, j] = -1;
                }
            }
            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }            
        }
        //controlling the finding minimum spaning tree
        //if the graf is not connected graf algorithm finished to solving
        public bool IsFinishedMST() {
            bool flag = true;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++)
                {
                    if (tempL[i, j] != -1)
                        flag = false;
                }
            }
            if (flag) { return true; }
            for (int i = 0; i < rank; i++)
            {
                if (C[i] != -1) {
                    return false;
                }
            }            
                return true;
        }
        //controlling connection of nodes and prevents the loop
        public void SetC(int a,int b) {//prevent loop
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == a)
                    C[i] = b;
            }        
        }
        //solution edges and nodes are writing sol array
        //and join the nodes
        public void SetSolution(int r, int c,int dis)
        {
            sol[r, c] = dis;
            if (C[r] < 0 || C[c] < 0)
            {
                if (C[r] < 0)
                {
                    SetC(C[c], C[r]);
                    C[c] = C[r];                    
                }
                else {
                    SetC(C[r], C[c]);
                    C[r] = C[c];                    
                }
            }
            else
            {
                C[r] = C[c] = (--connectedEdges);
            }
            Console.WriteLine(r + " " + c + " " + dis);
        }
        //algorithm
        public void KruskalSolving()
        {
            int dis=getMinimumDistance();
            SetSolution(row,column,dis);
            while (!IsFinishedMST())
            {
                dis=getMinimumDistance();
                if (C[row] == C[column] && C[row]<0)//loop
                    continue;
                else {
                   SetSolution(row, column, dis);
                }
            }
        }
    }

Not

    Kod'daki herhangi bir hata için çekinmeden mehmetaliecer@gmail adresine mail atabilirsiniz.

İyi çalışmalar

Mehmet Ali ECER

Ornek Uygulama ve Kodlar