kruskal's algorithm

 c implementation of kruskal's algorithm-minimum spanning tree

 header.h
int kruskal(int **a,int s,int v);


main.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include "header.h"

int main(){

int v,i,j,s;
int **a;
struct timeval tim;
double time_start,time_end,time1;
FILE *fp;
fp=fopen("input.txt","r");

fscanf(fp,"%d",&v);
printf("the number of vertex is :%d\n",v);

a=(int **)calloc(v,sizeof(int));
for(i=0;i<v;i++){

a[i]=(int *)calloc(v,sizeof(int));

}

for(i=0;i<v;i++){
    for(j=0;j<v;j++){
        fscanf(fp,"%d",&a[i][j]);          
        }
}

printf("The graph is :\n");
for(i=0;i<v;i++){
    for(j=0;j<v;j++){
        if(a[i][j]>0){
        printf("%d---->%d weight :%d\n",i,j,a[i][j]);
        }      
        }
}

gettimeofday(&tim,NULL);
time_start=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);

kruskal(a,0,v);
gettimeofday(&tim,NULL);
time_end=(double)tim.tv_sec +(double)(tim.tv_usec/1000000.0);
time1=time_end-time_start;
printf("Execution time taken is %1f\n",time1);
return 0;
}




 kruskal.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

struct sort{
int source;
int destination;
int weight;
};

int kruskal(int **a,int s,int v){

int *trace,i,j,k=0,m,n,*locator;
struct sort obj[100],temp;

trace=(int *)calloc(v,sizeof(int));
locator=(int *)calloc(v,sizeof(int));

for(i=0;i<v;i++){
trace[i]=i;
}
for(i=0;i<v;i++){
    for(j=0;j<v;j++){
            if(a[i][j]>0){
           
            obj[k].source=i;
            obj[k].destination=j;
            obj[k++].weight=a[i][j];           
            }
        }
}
       
for(i=0;i<k;i++){
    for(j=i+1;j<k;j++){
        if(obj[i].weight<obj[j].weight){
            temp=obj[i];
            obj[i]=obj[j];
            obj[j]=temp;
            }
        }
}


printf("the minimum spanning tree formed is :\n");


while(k>0){

k--;
m=obj[k].source;
n=obj[k].destination;

if(trace[m]!=trace[n] ){
printf("%d<----->%d \t weight :%d\n",m,n,obj[k].weight);

for(i=0;i<v;i++){
if(trace[i]==trace[m])
trace[i]=trace[n];
}
}
}
}

 


input.txt       

5
0 5 0 0 4
5 0 2 3 0
0 2 0 0 0
0 3 0 0 1
4 0 0 1 0

Copyright © C Program | Java | OpenGL Programming | Hadoop at Computaholics