Krushkals algorithm Code in C Language Code
#include #include #define max 50 void create_heap(int arr[][3],int n) { int k,heap,j; int temp[3]; for(int i=(n/2)-1;i>=0;--i) { k=i; temp[0]=arr[k][0]; temp[1]=arr[k][1]; temp[2]=arr[k][2]; heap=0; while( heap!=1 && ( (2*k +1) { j=2*k+1; if(j<n-1) <br=""> if(arr[j][2]>arr[j+1][2]) j++; if(arr[k][2]<arr[j][2]) <br=""> heap=1; else { arr[k][0]=arr[j][0]; arr[k][1]=arr[j][1]; arr[k][2]=arr[j][2]; k=j; heap=0; } } arr[k][0]=temp[0]; arr[k][1]=temp[1]; arr[k][2]=temp[2]; } } void input(int arr[][3]) { char ch; int s,d,w; int i=0; while(1) { printf("Do you want to enter any edge?:"); flushall(); scanf("%c",&ch); if(ch=='n'||ch=='N') break; printf("Source:"); flushall(); scanf("%d",&s); printf("Destination:"); flushall(); scanf("%d",&d); printf("Weight:"); flushall(); scanf("%d",&w); arr[i][0]=s; arr[i][1]=d; arr[i++][2]=w; } } void heap_delete(int arr[][3],int *n) { (*n)--; arr[0][0]=arr[*n][0]; arr[0][1]=arr[*n][1]; arr[0][2]=arr[*n][2]; create_heap(arr,*n); } int find(int i,int parent[20]) { while(parent[i]!=-1) i=parent[i]; return i; } void main() { clrscr(); int n; printf("Enter the no of veritces\n"); int edge[max][3],parent[max]; scanf("%d",&n); input(edge); int t[3]; //create_heap(edge,n); create_heap(edge,n); int u,v; int n1=n; int result[max][3]; for(int i=0;i<n;++i) <br=""> parent[i]=-1; for(i=0;i<n1-1;++i) <br=""> { t[0]=edge[0][0]; t[1]=edge[0][1]; t[2]=edge[0][2]; u=find(t[0],parent); v=find(t[1],parent); if(u!=v) { parent[u]=v; result[i][0]=t[0]; result[i][1]=t[1]; result[i][2]=t[2]; } heap_delete(edge,&n); } printf("S\tD\tW\n"); for(i=0;i<n1-1;++i) <br=""> printf("%d\t%d\t%d\n",result[i][0],result[i][1],result[i][2]); getch(); }
Leave a Reply