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