#include <stdio.h>
#include<stdlib.h>
#include<time.h>
int visited[100]={0};
struct edge{
int u,v,w;
};
int present(int x[2500],int n,int ele){
int i;
for(i=0;i<n;i++){
if(ele == x[i])
return 1;
}
return 0;
}
int main()
{
clock_t start, end;
float time_taken;
start = clock();
int no,i,j,k2,flag,k=0,cost = 0,a[50][50];
FILE *f1;
struct edge e[2500],temp;
f1=fopen("matrix.txt","w");
printf("Enter no of edges ");
scanf("%d",&no);
/*for(i=0;i<no;i++){
printf("Enter Starting Vertex,Ending Vertex and Weight of edge ");
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}*/
for(i=0;i<no;i++)
{
for(j=i+1;j<no;j++)
a[i][j]=rand()%20;
}
for(i=0;i<no;i++)
a[i][i]=0;
for(i=0;i<no;i++)
{
for(j=0;j<i;j++)
a[i][j]=a[j][i];
}
for(i=0;i<no;i++)
{
for(j=0;j<no;j++)
{
fprintf(f1,"%d\t",a[i][j]);
}
fprintf(f1,"\n");
}
for(i=0;i<no;i++)
{
for(j=0;j<i;j++)
{
if(a[i][j]!=0)
{
e[k].u=i;
e[k].v=j;
e[k].w=a[i][j];
k++;
}
}
}
for(i=1;i<no;i++){
for(j=0;j<no-i;j++){
if(e[j].w > e[j+1].w){
temp = e[j];
e[j] = e[j+1];
e[j+1] = temp;
}
}
}
k2 = 0;
for(i=0;i<no;i++){
flag = 0;
if(!present(visited,k2,e[i].u)){
visited[k2++] = e[i].u;
flag = 1;
}
if(!present(visited,k2,e[i].v)){
visited[k2++] = e[i].v;
flag = 1;
}
if(flag == 1) cost+=e[i].w;
}
printf("\nCost is %d\n",cost);
end = clock();
time_taken = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("Time taken = %f",time_taken);
printf("Finally %d %d",k,no);
return 0; }
