Verilen bir grafın minimum spanning tree’sinin bulunması en düşük maliyet ile bütün noktaların kapsanması açısından özellikle istasyonlar arasında ağ kurulumunda önem taşır. Bu çalışmada Kruskal’ın algoritmasını kullanarak basit bir minimum spanning tree implementasyonu yapılmıştır. Kaynaktaki graf n tane edge’den(u,v ve ağırlık değeri içeren bir struct) oluşan bir dizi şeklinde gösterilmiştir. MST bulma aşamasında hangi noktaların hangi alt graflara bağlandığını takip edebilmek için label[] adlı bir dizi kullanılmıştır. Derste de gördüğümüz bu algoritma ile graf üzerindeki bir MST’yi kolaylıkla bulabilmekteyiz.

Akış Diyagramı:

Kaynak Kodlar:

#include <stdio.h>
#include <stdlib.h>
#define size 50

struct graphNode{
       int u,v,weight;
       };

int main(){
    int label[size], numOfEdges, numOfNodes, i, k, u, v, temp, edgeCount=0, totalWeight=0;
    struct graphNode graph[size], tempNode;

    printf("Enter the number of the edges: "); scanf("%d",&numOfEdges);
	printf("Enter the number of the nodes: "); scanf("%d",&numOfNodes);
    for(i=0;i<numOfEdges;i++){
                              printf("u: "); scanf("%d",&graph[i].u);
                              printf("v: "); scanf("%d",&graph[i].v);
                              printf("weight: "); scanf("%d",&graph[i].weight);
                              printf("\n");
                              }

	for(k=0;k<numOfEdges-1;k++)
		for(i=0;i<numOfEdges-1;i++)
			if(graph[i].weight>graph[i+1].weight){
				tempNode=graph[i];
				graph[i]=graph[i+1];
				graph[i+1]=tempNode;
			}

    for(i=0;i<size;i++) label[i]=0;

    i=0;
    while(edgeCount<numOfNodes-1){
                                  u=graph[i].u;
                                  v=graph[i].v;
                                  if((label[u]+label[v])==0){
															 edgeCount++;
                                                             label[u]=label[v]=edgeCount;
                                                             totalWeight+=graph[i].weight;
                                                             printf("u:%d, v:%d, weight:%d\n",u,v,graph[i].weight);
                                                             }
                                  else if((label[u]*label[v])==0){
                                       edgeCount++;
                                       label[u]=label[v]=(label[u]+label[v]);
                                       totalWeight+=graph[i].weight;
                                       printf("u:%d, v:%d, weight:%d\n",u,v,graph[i].weight);
                                       }
                                  else if(label[u]!=label[v]){
                                       edgeCount++;
									   temp=label[v];
                                       for(k=1;k<=numOfNodes;k++)
										if(label[k]==temp) label[k]=label[u];

                                       totalWeight+=graph[i].weight;
                                       printf("u:%d, v:%d, weight:%d\n",u,v,graph[i].weight);
                                       }
                                  i++;
                                  }

    printf("\nTotal Weight: %d\n",totalWeight);
    system("pause");
    return 0;
    }