#include<stdio.h>
#include<stdlib.h>
#include<string.h>


#define INFINITY 10000
#define max_name 50
#define MAX_VERTEX_NUM 50

typedef char vertex[max_name];
typedef int adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
   int adjvex;
   int lowcost;
 }ClosEdge[MAX_VERTEX_NUM];

typedef  struct
{
   int vexs[MAX_VERTEX_NUM];
   adjMatrix arcs;
   int arcnum,vexnum;
}MGraph;
int MAX;


void CreateMarph(MGraph G)
{
  int lowcost,i,j,k,p,MAX;
  int v1,v2;
  printf("请输入无向图的顶点数和边数;");
  scanf("%d%d",&G.vexnum,&G.arcnum);
  for(i=0;i<G.vexnum;i++)
  {      
    for(j=0;j<G.vexnum;j++)
    G.arcs[i][j]=INFINITY;
  }
 for(p=0;p<G.vexnum;p++)
  {
        printf("第%d个顶点的序号：",p+1);
        scanf("%d",&G.vexs[p]);
        printf("%d",&G.vexs[p]);
  }
  
printf("\n          请确定各条弧的信息       \n");
for(k=0;k<G.arcnum;k++)
{
   printf("请输入第%d弧的两个起始顶点(序号递增输入)和其权值为:",k+1);
   for(;;)
   {
         scanf("%d%d%d",&v1,&v2,&lowcost);
         if((v1>=1&&v1<=G.vexnum)&&(v2<=G.vexnum))
               break;
         else
                  printf("输入有误，不存在该顶点，请重新输入\n");
    }
        i=LocateVex(G,v1);      //找到两个顶点在邻接矩阵中的位置
        j=LocateVex(G,v2);
        G.arcs[i][j]=lowcost;         
        G.arcs[j][i]=G.arcs[i][j];
}      
 for(i=0;i<G.vexnum;i++)
  {      
    for(j=0;j<G.vexnum;j++)
       {printf("    %d",&G.arcs[i][j]);}
       printf("\n");
  }
printf(" -----------\n");
}


void MiniSpanTree_PRIM(MGraph G,int u)
{
 ClosEdge closedge;
 int i,j,k;
 printf("最小代价生成树:\n");
 for(j=1;j<=G.vexnum;j++)
   if(j!=u)
     {closedge[j].adjvex=u;
      closedge[j].lowcost=G.arcs[u][j];
     }
 closedge[u].lowcost=0;
 for(i=1;i<G.vexnum;i++)
   {
      k=Minimum(closedge,G.vexnum);
      printf("%d,%d\n",&closedge[k].adjvex,&k);
      closedge[k].lowcost=0;  
      for(j=1;j<=G.vexnum;j++)
      if(G.arcs[k][j]<closedge[j].lowcost)
       {
          closedge[j].adjvex=k;
          closedge[j].lowcost=G.arcs[k][j];
       }
    }
    return 1;
}


int Minimum(ClosEdge cl,int vnum)
{
 int i;
 int w,p;
 w=INFINITY;
 for(i=1;i<=vnum;i++)
  if(cl[i].lowcost!=0&&cl[i].lowcost<w)
     {
       w=cl[i].lowcost;
       p=i;
     }
 return p;
}


 int LocateVex(MGraph G,vertex v)
 {
    int t,i;
    for(i=0;i<G.vexnum;i++)
    {
      if(G.vexs[i]==v)
      t=i;
     }
      return t;
 }


void main()
{
    int u;
    MGraph G;
    CreateMarph(G);
    printf("从哪一顶点开始:");
    scanf("%d",&u);
    MiniSpanTree_PRIM(G,u);

}