Prim's Algorithm

SOURCE CODE:
#include<stdio.h>
int visited[20]={0},arr[20][20];
int i,j,n,near=0,min,mincost=0,i_store,j_store;
int prims(){
while(near < n){
near++;
for(i=0,min=9999;i<n;i++)
for(j=0;j<n;j++)
if(arr[i][j] < min)
if(visited[i]!=0){
min=arr[i][j];
i_store=i;
j_store=j;
}
if(visited[i_store]==0 || visited[j_store]==0){
printf("Edge %d : %d--->%d cost is %d\n",near,i_store+1,j_store+1,min);
mincost+=min;
visited[j_store]=1;
}
arr[i_store][j_store]=9999;
arr[j_store][i_store]=9999;
}
return mincost;
}
int main(){

printf("Enter # of vertices :\n");
scanf("%d",&n);
printf("Enter the adjacency matrix :\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&arr[i][j]);
if(arr[i][j]==0)
arr[i][j]=9999;//assuming max value
}
visited[0]=1;
printf("Mininum cost = %d\n",prims());
return 0;

}

OUTPUT :
Enter # of vertices :
7
Enter the adjacency matrix :
0 28 0 0 0 10 0
28 0 16 0 0 0 14
0 16 0 12 0 0 0
0 0 12 0 22 0 18
0 0 0 22 0 25 24
10 0 0 0 25 0 0
0 14 0 18 24 0 0

Edge 1 : 1--->6 cost is 10
Edge 2 : 6--->5 cost is 25
Edge 3 : 5--->4 cost is 22
Edge 4 : 4--->3 cost is 12
Edge 5 : 3--->2 cost is 16
Edge 6 : 2--->7 cost is 14

Mininum cost = 99

Comments