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}, };
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, 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, 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
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.)
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
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.
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); } } } }
Kod'daki herhangi bir hata için çekinmeden mehmetaliecer@gmail adresine mail atabilirsiniz.
İyi çalışmalar
Mehmet Ali ECER