/*  PRIM算法  */
#include<stdio.h>
#include<string.h>

#define INFINITY  10000  /*  最大值10000  */
#define MAX_VERTEX_NUM 20  /*  最大頂點(diǎn)個(gè)數(shù)  */
#define Status int

typedef enum GraphKind{
    DG,  /*  有向圖   */
    DN,  /*  有向網(wǎng)   */
    AG,  /*  無(wú)向圖   */
    AN  /*  無(wú)向網(wǎng)   */
}GraphKind;

typedef struct ArcCell{
    int adj;  /*  adj對(duì)無(wú)權(quán)圖用1或0表示是否相鄰；對(duì)帶權(quán)圖表示權(quán)值類(lèi)型  */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{
    char        vexs[MAX_VERTEX_NUM];  /*  頂點(diǎn)向量  */
    AdjMatrix  arcs;  /*  鄰接矩陣  */
    int        vexnum,arcnum;  /*  圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)  */
    GraphKind  kind;  /*  圖的種類(lèi)標(biāo)志  */
}MGraph;

typedef struct{
    char adjvex;
    int lowcost;
}closedge[MAX_VERTEX_NUM];


Status CreateUDC(MGraph *G)
  /*  采用數(shù)組（鄰接矩陣）表示法，構(gòu)造無(wú)向網(wǎng)G  */
{
  char v1,v2;
  int i,j,k,l,weight;  /*  weight表示邊的權(quán)值  */

  printf("Please input the number of the vertex and arc:\n");

  printf("vertex:");  /*  輸入頂點(diǎn)數(shù)  */
  scanf("%d",&G->vexnum);

  printf("arc:");  /*  輸入弧數(shù)  */
  scanf("%d",&G->arcnum);

  printf("Please input the vertex:");

  getchar();
  for(i=0;i<G->vexnum;i++)  /*  構(gòu)造頂點(diǎn)向量  */
    G->vexs[i]=getchar();
  for(i=0;i<G->vexnum;i++)  /*  初始化鄰接矩陣  */
    for(j=0;j<G->vexnum;j++)
      G->arcs[i][j].adj=INFINITY;

  printf("Please input the two vertexs connecting one arc and the weight of the arc:\n");
  for(k=0;k<G->arcnum;k++)/*  構(gòu)造鄰接矩陣  */
    {
      getchar();
      scanf("%c%c%d",&v1,&v2,&weight);  /*  輸入一條邊依附的頂點(diǎn)及權(quán)值  */
      for(l=0;l<G->vexnum;l++)  /*  確定v1在G中位置  */
        if(v1==G->vexs[l])
          {
            i=l;
            break;
          }
      for(l=0;l<G->vexnum;l++)  /*  確定v2在G中位置  */
        if(v2==G->vexs[l])
          {
            j=l;
            break;
          }
      G->arcs[i][j].adj=weight;  /*  弧<v1,v2>的權(quán)值  */
      G->arcs[j][i].adj=G->arcs[i][j].adj;  /*  置<v1,v2>的對(duì)稱(chēng)弧<v2,v1>  */
    }
  return 1;
}  /*  CreateUDC()  */


void MinispanTree_PRIM(MGraph *G,char u)
  /*  用prim算法從第u個(gè)定點(diǎn)出發(fā)構(gòu)造G的最小生成樹(shù)T,輸出T的各條邊  */
{
  int i,j,k;
  closedge close;

  for(i=0;i<G->vexnum;i++)  /*  用k記錄u在G中位置  */
    if(u==G->vexs[i])
      {
        k=i;
        break;
      }  /*  if  */
  for(j=0;j<G->vexnum;j++)
    {
      if(j!=k)
        {
          close[j].adjvex=G->vexs[k];  /*  將頂點(diǎn)k放入close[j]  */
          close[j].lowcost=G->arcs[k][j].adj;  /*  將與k連接的鄰接邊的權(quán)值放入close[j].lowcost  */
        }  /*  if  */
    }  /*  for  */
  close[j].lowcost=10000;
  close[j].adjvex='\0';
  close[k].lowcost=0;  /*  初始，U={u}  */
  close[k].adjvex=u;
  for(i=1;i<G->vexnum;i++)  /*  選擇其余G->vexnum-1個(gè)頂點(diǎn)  */
    {
      k=Minimum(close);  // 求出T的下一個(gè)結(jié)點(diǎn)：第k頂點(diǎn)  */
      printf("%c",close[k].adjvex);
      printf("--->");
      printf("%c  ",G->vexs[k]);
      printf("%d\n",close[k].lowcost);
      close[k].lowcost=0;  /*  將第k點(diǎn)并入U(xiǎn)集  */
      for(j=0;j<G->vexnum;j++)  /*  新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊  */
        {
          if(G->arcs[k][j].adj<close[j].lowcost)
            {
              close[j].adjvex=G->vexs[k];
              close[j].lowcost=G->arcs[k][j].adj;
            }  /*  if  */
        }  /*  for  */
    }  /*  for  */
}  /*  MinispanTree_PRIM()  */



Status Minimum(closedge close)
  /*  從close.lowcost中選出最小的權(quán)值所代表的那個(gè)沒(méi)有被并入u的頂點(diǎn)  */
{
  int j1,client,j2;

  j1=0;
  client=10000;
  while(close[j1].adjvex!='\0')
    {
      if(client>close[j1].lowcost&&close[j1].lowcost!=0)
        {
          client=close[j1].lowcost;
          j2=j1;
        }  /*  if  */
      j1++;
    }  /*  while  */
  return j2;
}  /*  Minimum()  */


main()
{
  MGraph *G;
  int i,j;
  
  G=(MGraph*)malloc(sizeof(MGraph));
  CreateUDC(G);
  MinispanTree_PRIM(G,'a');
}