#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define infinity 30000
#define MAX 20

int s[MAX];

typedef struct ArcCell{
  int adj;
}AecCell,AdjMatrix[MAX][MAX];

typedef struct Mgraph{
  char vex[MAX];
  AdjMatrix arcs;
  int vexnum,arcnum;
}Mgraph;

int Create(Mgraph&G)
{
   int i,j,value,n=0;
   int v1,v2; 
   int LocateVex(Mgraph G,char name);//G.vexnum=3;G.arcnum=3;
   printf("請輸入結點數:");
   scanf("%d",&G.vexnum);
   printf("請輸入弧數:");
   scanf("%d",&G.arcnum);
   //printf("input the vertex:");
   /*for(i=0;i<G.vexnum;i++)
      scanf("%c",&G.vex[i]);*/
    //G.vex[0]='a';
    //G.vex[1]='b';
    //G.vex[2]='c';
   for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
       G.arcs[i][j].adj=infinity;
   printf("請輸入弧的權值:<like this:0 1 n>\n");
   for(j=0;j<G.arcnum;j++)
   {  
	  scanf("%d %d %d",&v1,&v2,&value);
      //i=LocateVex(G,v1);
      //j=LocateVex(G,v2);printf("%d,%d\n",i,j);
      G.arcs[v1][v2].adj=G.arcs[v2][v1].adj=value;
   }
   return 1;
}

int LocateVex(Mgraph G,char name)
{
  int i;printf("%c",name);
  for(i=0;G.vex[i]!=name;i++){}printf("%d",i);
  return i;
}

/*void createMGraph(Mgraph *G)
{int i,j,k,w;
   scanf(“%d %d”,&G->vexnum,&G->arcnum);
   for(i=0; i<G->vexnum; i++) G->vex[i]=getchar();
   for(i=0; i<G->vexnum; i++)
       for(j=0; j<G->vexnum; j++)  G->arcs[i][j]=infinity;
   for(k=0; k<G->zrcnum; k++)
        { scanf(“%d %d %d”,&i,&j,&w);
           G->arcs[i][j]=w;   G->arcs [j][i] =w;}
}*/
       
void prim(Mgraph G,int v0,int adjvex[],int lowcost[])
{ 
  int v,i,w,min;
  for(v=0;v<G.vexnum;v++)
  {s[v]=0;
   lowcost[v]=G.arcs[v0][v].adj;
   if(lowcost[v]<infinity)
       adjvex[v]=v0;
   else adjvex[v]=-1;
  }
  lowcost[v0]=0;
  s[v0]=1;
  for(i=1;i<G.vexnum;++i)
  { min=infinity;
    for(w=0;w<G.vexnum;++w)
      if(s[w]==0)   //w∈V-S
         if(lowcost[w]<min)
         {v=w;
          min=lowcost[w];
         }
    s[v]=1;//將v加入S
    for(w=0;w<G.vexnum;++w)//調整其余在V-S的點
      if(s[w]==0 &&(G.arcs[v][w].adj<lowcost[w]))
          { lowcost[w]= G.arcs[v][w].adj;
            adjvex[w]=v; 
          }
  }
}

int main(int argc, char *argv[])
{
  int i,j;
  Mgraph G;
  int adjvex[MAX];
  int lowcost[MAX];
  Create(G);
  printf("頂點如下所示:\n");
  i=0;
  prim(G,i,adjvex,lowcost);
  for(j=1;j<G.vexnum;j++)
     printf("v%d -- v%d權值=%d;\n",j,adjvex[j],lowcost[j]);
        
  system("PAUSE");	
  return 0;
}