#include<stdio.h>
int **cost,n,**t,v,*s;
int find(int *);
int prim(int *);
int main()
{
int i,j,temp;
printf("Enter no.of vertices in graph\n");
scanf("%d",&n);
cost=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
cost[i]=(int *)malloc(n*sizeof(int));
printf("Enter distances\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
cost[i][j]=1000;
else
cost[i][j]=10000;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(cost[i][j]==10000)
{
scanf("%d",&temp);
cost[j][i]=temp;
cost[i][j]=temp;
}
}
}
int *near=(int *)malloc(n*sizeof(int *));
t=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
t[i]=(int *)malloc(2*sizeof(int));
printf("\nMinimum cost=%d\n",prim(near));
for(i=0;i<n;i++)
printf("%d %d\n",t[i][0]+1,t[i][1]+1);
}
int find(int *near)
{
int i,min=10000,j;
for(i=0;i<n;i++)
{
if(near[i]!=-1&&(cost[i][near[i]]<min))
{
j=i;
min=cost[i][near[i]];
}
}
return j;
}
int prim(int *near)
{
int mincost=0,j,k,i;
for(i=1;i<n;i++)
near[i]=0;
near[0]=-1;
for(i=1;i<n;i++)
{
j=find(near);
t[i][0]=j;
t[i][1]=near[j];
mincost+=cost[j][near[j]];
near[j]=-1;
for(k=1;k<n;k++)
{
if(near[k]!=-1&&(cost[k][near[k]]>cost[k][j]))
near[k]=j;
}
}
return mincost;
}
int **cost,n,**t,v,*s;
int find(int *);
int prim(int *);
int main()
{
int i,j,temp;
printf("Enter no.of vertices in graph\n");
scanf("%d",&n);
cost=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
cost[i]=(int *)malloc(n*sizeof(int));
printf("Enter distances\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
cost[i][j]=1000;
else
cost[i][j]=10000;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(cost[i][j]==10000)
{
scanf("%d",&temp);
cost[j][i]=temp;
cost[i][j]=temp;
}
}
}
int *near=(int *)malloc(n*sizeof(int *));
t=(int **)malloc(n*sizeof(int *));
for(i=0;i<n;i++)
t[i]=(int *)malloc(2*sizeof(int));
printf("\nMinimum cost=%d\n",prim(near));
for(i=0;i<n;i++)
printf("%d %d\n",t[i][0]+1,t[i][1]+1);
}
int find(int *near)
{
int i,min=10000,j;
for(i=0;i<n;i++)
{
if(near[i]!=-1&&(cost[i][near[i]]<min))
{
j=i;
min=cost[i][near[i]];
}
}
return j;
}
int prim(int *near)
{
int mincost=0,j,k,i;
for(i=1;i<n;i++)
near[i]=0;
near[0]=-1;
for(i=1;i<n;i++)
{
j=find(near);
t[i][0]=j;
t[i][1]=near[j];
mincost+=cost[j][near[j]];
near[j]=-1;
for(k=1;k<n;k++)
{
if(near[k]!=-1&&(cost[k][near[k]]>cost[k][j]))
near[k]=j;
}
}
return mincost;
}
No comments:
Post a Comment