New Want to Write for Computaholics ? if Yes Contact us at "contact@computaholics.in"

prims algorithm for minimum spanning tree

 prims algorithm for minimum spanning tree

header.c 
int minkey(int **a,int key[],int v,int trace[]);
int prim(int **a,int s,int v);



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

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

int key[v],parent[v],i,pointer;
int u,*trace;

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

for(i=0;i<v;i++){
parent[i]=-1;
key[i]=INT_MAX;
}

key[s]=0;

for(pointer=0;pointer<v;pointer++){
u=minkey(a,key,v,trace);
trace[u]=1;


for(i=0;i<v;i++){
    if(a[u][i]>0 && trace[i]==0 && a[u][i]<key[i]){
  
    parent[i]=u;
    key[i]=a[u][i];
  
    }
    }
}

printf("the spanning tree is :\n");
for(i=1;i<v;i++){

printf("%d<---->%d\t weight :%d\n",i,parent[i],a[i][parent[i]]);

}
}



 main.c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<sys/time.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);

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("enter the source node\n");
scanf("%d",&s);

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);

prim(a,s,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;
}


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

int minkey(int **a,int key[],int v,int trace[]){

int i,min=INT_MAX,pos;

for(i=0;i<v;i++){
if(key[i]<min && trace[i]==0){
min=key[i];
pos=i;
        }
}
return pos;
}















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