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