zuixiaoshengchengshu.cpp

使用贪心算法编程

# include <stdio.h>
# define inf 1000
# define max  50
void prim(int g[max][max],int n)
{
	int lowcost[max],closest[max];
	int i,j,k,min;
	for(i=2;i<=n;i++)
	{
		lowcost[i]=g[1][i];
		closest[i]=1;
	}
	lowcost[1]=0;
	for(i=2;i<=n;i++)
	{
		min=inf;
		k=0;
		for(j=2;j<=n;j++)
			if((lowcost[j]<min)&&(lowcost[j]!=0))
			{
				min=lowcost[j];
				k=j;
			}
		printf("(%d,  %d),    %d\t",closest[k],k,min );
		lowcost[k]=0;
		for(j=2;j<=n;j++)
			if(g[k][j]<lowcost[j])
		{
				lowcost[j]=g[k][j];
				closest[j]=k;
		}
		printf("\n");
	}
}

void main()
{ 
	int g[max][max];
	int n,i,j;
	printf("all point=");
	scanf("%d",&n);
	printf("point point quan\n");
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++ )
			scanf("%d",&g[i][j]);
		printf("small tree:\n");
		prim(g,n);
	
	
}