Kruskal Algoritması(Minimum Spanning Tree)
Özet :
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.
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
Yazgelistir.com