cpp1.cpp

数据结构的一些基本的相关的试验

#include<stdio.h>
#define m 30
#define max 99
struct mgraph
{
	int adjmatrix[m][m];
};
mgraph g;

void buildnet(mgraph& g,int n)                 //构造n个城市的邻接矩阵
{
	int i,j;
	int data;
	printf("请填入各城市之间的公路的工程造价\n");
	printf("如造价很高就填100\n");
	for(i=1;i<=n;i++)
	{
		j=i+1;
		for(;j<=n;j++)
		{
			if(i!=j)
			{
			printf("请输入从城市%d到城市%d公路的工程造价:",i,j);		
			scanf("%d",&data);
            g.adjmatrix[i][j]=data;
			g.adjmatrix[j][i]=g.adjmatrix[i][j];
			}
		}
	}
   for(i=1;i<=n;i++)
   {
	   for(j=1;j<=n;j++)
	 {
		 printf("%d ",g.adjmatrix[i][j]);
		 
	 }
	   printf("\n");
   }
}


void prim(mgraph g,int k,int n)
{
	int i,j,min,p,money=0;
	struct
	{
		int adjvex;
		int lowcost;
	}closedge[m];
for(i=1;i<=n;i++)
   if(i!=k)                               //如果i城市是k城市
   {
	   closedge[i].adjvex=k;
	   closedge[i].lowcost=g.adjmatrix[k][i];
   }
closedge[k].lowcost=0;
for(i=1;i<n;i++)
{
	p=1;
	min=max;
	for(j=1;j<=n;j++)
		if(closedge[j].lowcost!=0&&closedge[j].lowcost<min)
		{
			min=closedge[j].lowcost;
			p=j;
		}
	printf("%d--%d  %d\n",closedge[p].adjvex,p,min);     //输出此时在未加入生成树的最小的权值
	money=closedge[p].lowcost+money;
closedge[p].lowcost=0;
for(j=1;j<=n;j++)

	if(g.adjmatrix[p][j]<closedge[j].lowcost)
	{
		closedge[j].lowcost=g.adjmatrix[p][j];
		closedge[j].adjvex=p;
	}
}
     
printf("\n输出最小工程造价:%d\n",money);
}

void main()
{
   int n,k;
   printf("请输入城市的数目:");
   scanf("%d",&n);
   buildnet(g,n);
   printf("请输入从第几个城市开始进行构造最小生成树:");
   scanf("%d",&k);
   prim(g,k,n);
}