#include<stdio.h>
#include<stdlib.h>
#define M 20
#define INFINITY 100
	int V_num,E_num;
	char vetex[M];
struct 
{   int  adjvex ;     /*   边所依附于U中的顶点   */
int  lowcost ;    /*   该边的权值   */
}closedge[M] ;
typedef struct MSTEdge
{  int  vex1, vex2 ;    /*  边所依附的图中两个顶点 */
   int  weight ;     /*  边的权值  */
}MSTEdge ;
MSTEdge *Prim_MST(int W[][M] , int u)
      /*   从第u个顶点开始构造图G的最小生成树   */
{  MSTEdge *TE;  //  存放最小生成树n-1条边的数组指针
	int j , k , v , min ;
	for (j=0; j< V_num; j++)
	{ 
		closedge[j].adjvex=u; 
		closedge[j].lowcost=W[j][u]  ;
		//printf("closedge[%d].adjvex=%-2d,closedge[%d].lowcost=%-4d\n",j,closedge[j].adjvex,j,closedge[j].lowcost);
	}    /*   初始化数组closedge[n]  */ 
		closedge[u].lowcost=0;      /*   初始时置U={u}  */ 
		TE=(MSTEdge *)malloc(( V_num-1)*sizeof(MSTEdge)) ;
	for (j=0; j< V_num-1; j++)
	{ 
		min= INFINITY;
		k=u;
		for (v=0; v< V_num; v++) 
		if(closedge[v].lowcost!=0&&closedge[v].lowcost<min)
			       {  min=closedge[v].lowcost ; k=v ;  }
	//	printf("k=%d\n",k);
		
		TE[j].vex1=closedge[k].adjvex ; 
		TE[j].vex2=k ;
		TE[j].weight=closedge[k].lowcost ;
	
		closedge[k].lowcost=0 ;      /*   将顶点k并入U中  */
		for (v=0; v< V_num; v++)
			if (W[v][k]<closedge[v]. lowcost&&closedge[v]. lowcost!=0)
			   {  closedge[v].lowcost=W[v][k] ;
				   closedge[v].adjvex=k ; 
			   }  /*   修改数组closedge[n]的各个元素的值   */
	}
	return(TE) ;
}   /*   求最小生成树的Prime算法   */ 


main()
{

	char source;
	 MSTEdge *TE; 
	int i,k,j,w[M][M],SumWeight=0,u;
	printf("输入顶点标识以“#”号作为结束：\n");
	i=0;
	do{
			 vetex[i]=getchar();
			 i++;
	
	}while(vetex[i-1]!='#');
	V_num=i-1;
	printf("请输入%dX%d的带权邻接矩阵：\n",V_num,V_num);
		printf("    ");
	for(i=0;i<V_num;i++)
		printf("%-4c",vetex[i]);
	putchar('\n');
	for(i=0;i<V_num;i++)
	{
		printf("%-4c",vetex[i]);
		for(j=0;j<V_num;j++)
			scanf("%d",&w[i][j]);
		putchar('\n');
	}
	printf("带全邻接矩阵为：\n");
	for(i=0;i<V_num;i++)
	{
		
		for(j=0;j<V_num;j++)
		printf("%-5d",w[i][j]);
		putchar('\n');
	}
	u=getchar();
	printf("输入搜索起点u:");
	scanf("%c",&source);
	for(i=0;i<V_num;i++)
		if(vetex[i]==source)break;
	if(i<V_num) u=i;
	TE=Prim_MST(w,u);
	printf("普利姆最小生成树中的边包括：\n");
	for(i=0;i<V_num-1;i++)
	{
		printf("第%d条边为：<%c,%c>,权重为:%d.\n",i+1,vetex[(TE+i)->vex1],vetex[(TE+i)->vex2],TE[i].weight);
		SumWeight+=(TE+i)->weight;
	}
	printf("普利姆最小生成树的带全路径和为：%d.\n\n",SumWeight);
}