#include<stdio.h>
int cost[10][10];
int visited[10] = {0};
int min=0, min_cost=0;
int n, ne=1, a=0, b=0, u=0, v=0, i, j;
int main()
{
printf("Enter number of vertices in Graph : ");
scanf("%d", &n);
printf("Enter Matrix with weights : \n");
for(i=1 ; i<=n ; i++)
{
for(j=1 ; j<=n ; j++)
{
scanf("%d", &cost[i][j]);
if(cost[i][j]==0){
cost[i][j] = 999;
}
}
}
visited[1] = 1;
while(ne < n)
{
for(i=1, min=999 ; i<=n ; i++)
{
for(j=1 ; j<=n ; j++)
{
if(cost[i][j] < min)
{
if(visited[i] != 0)
{
min = cost[i][j];
a=u=i;
b=v=j;
}
}
}
}
if(visited[u]==0 || visited[v]==0)
{
printf("Edge %d : (%d to %d) cost : %d \n", ne++, a, b, min);
min_cost = min_cost + min;
visited[b]=1;
}
cost[a][b] = cost[b][a] = 999;
}
printf("Minimum cost : %d \n", min_cost);
return 0;
}
No Comments