zhang.c

求解最小生成树问题

#include <stdio.h>
#define N 50
void init(float c[N][N],int y[N],int m)
{
	int i,j;
	
	for(i=0;i<m;i++)
	{
		y[i]=0;
		printf("请输入矩阵的第%d行:\n",i);
		for(j=0;j<m;j++)
		{
			scanf("%f",&c[i][j]);
			
			}
		}
		y[0]=1;
	}
	void print(int x[N][N],int m)
	{
		int i,j;
		for(i=0;i<m;i++)
		{
			printf("\n");
			for(j=0;j<m;j++)
			{
				printf("%d  ",x[i][j]);
				}
		}
		printf("\n");
		
		}
void main()
{
float c[N][N];
	//float c[5][5]={{0 ,9 ,1000000 ,3, 1000000},{9 ,0, 2, 1000000, 7 },{1000000 ,2 ,0 ,2 ,4},{3, 1000000 ,2 ,0 ,1000000},{1000000 ,7 ,4 ,1000000 ,0}};
	 float a;
     int x[N][N]={0};
     int y[N],q=1,i=0,j=0;     
     int m,s,t;
     printf("请输入矩阵的行数:\n");
          scanf("%d",&m);
     init(c,y,m);
	 
	
	while(q==1)
	{
		q=0;
		a=1000;
		for(i=0;i<m;i++)
		{
			for(j=0;j<m;j++)
			{
				if(y[i]==1&&y[j]==0)
				{
					q=1;
					if(a>=c[i][j]&&y[j]==0)
					{
						a=c[i][j];
					    s=i;
					    t=j;
					}
		         }
				 
			}

		}
		
		x[s][t]=1;
		y[t]=1;
		}
	  print(x,m);
}