Prims algorithm Code in C Language
Write a program for Prims algorithm Code in C Language for finding Minimum spanning tree.
Prims algorithm Code
#include #include #define max 50 #define infinity 32767 void input(int adj[max][max],int n) { int i,j; char ch; for(i=0;i<n;++i) <br=""> { for(j=0;j<n;++j) <br=""> { adj[i][j]=infinity; } } int s,d,w; while(1) { printf("Do You want to enter another edge\n"); flushall(); scanf("%c",&ch); if(ch=='y'||ch=='Y') { flushall(); printf("Source:"); scanf("%d",&s); printf("Dest:"); scanf("%d",&d); printf("Weight:"); scanf("%d",&w); adj[s][d]=w; adj[d][s]=w; } else break; } } int check(int arr[],int pos) { while(1) { if(arr[pos]!=-1) pos=arr[pos]; else return pos; } //return -1; } void print(int mst[],int n) { printf("SOURCE\tDEST\tWEIGHT\n"); for(int i=0;i<(n/3);++i) { for(int j=i*3;j<(i+1)*3;++j) { printf("%d\t",mst[j]); } printf("\n"); } } void main() { int adj[max][max]; int n; clrscr(); printf("Enter the no of vertices\n"); scanf("%d",&n); input(adj,n); int visited[max]; visited[0]=-1; for(int i=1;i<n;++i) <br=""> { visited[i]=0; } int min=infinity; int pos,ptr=0; int mst[max]; for(int j=0;j<n-1;++j) <br=""> { min=infinity; for(i=0;i<n;++i) <br=""> { if(visited[i]!=-1) { if(min>adj[i][visited[i]]) { pos=i; min=adj[i][visited[i]]; } } } mst[ptr++]=pos; mst[ptr++]=visited[pos]; mst[ptr++]=adj[pos][visited[pos]]; visited[pos]=-1; for(i=0;i<n;++i) <br=""> { if(visited[i]!=-1 && adj[i][pos]<adj[i][visited[i]] )="" <br=""> { visited[i]=pos; } } } print(mst,ptr); getch(); }
Leave a Reply