#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define mvern 20
#define flase -1
#define truth 1
typedef char vertextype;
typedef struct vnode adjlist[mvern];
typedef struct arcnode
{
    int adjvex;
    struct arcnode *nextarc;
    int info;/*权值*/
}arcnode;

typedef struct vnode
{
    vertextype data[2];
    arcnode *firstarc;
}vnode;

typedef struct algraph
{
    adjlist vertices;
    int vexnum,arcnum;
    int kind;
}algraph;

struct closedge
{
   vertextype adj[2];
   int lowcost;
};

struct closedge min[mvern];

void creatal(algraph *g)
{
   arcnode *s;
   int i,j,m,n,ifo;
   char *c1,*c2;
   printf("\nPlease input the vexn and arcn:\n");
   scanf("%d%d",&g->vexnum,&g->arcnum);
   fflush(stdin);
   printf("g->vexnum=%d g->arcnum=%d\n",g->vexnum,g->arcnum);
   printf("\nPlease input the vexdata:\n");
   for(i=1;i<=g->vexnum;i++)
    {
        printf("\ni=%d",i);
        scanf("%s",&g->vertices[i].data);
        g->vertices[i].firstarc=NULL;
        fflush(stdin);
    }
   for(i=1;i<=g->vexnum;i++)
    {
        printf("%s %d\n",g->vertices[i].data,g->vertices[i].firstarc);
    }
  printf("\nPlease input the vm->vn and info:\n");
  fflush(stdin);
  for(i=1;i<=g->arcnum;i++)
   {
      scanf("%s",&c1);
      m=locate(g,&c1);
      scanf("%s",&c2);
      n=locate(g,&c2);
      fflush(stdin);
      scanf("%d",&ifo);
      s=(struct arcnode *) malloc (sizeof(struct arcnode));
      s->adjvex=n;
      s->info=ifo;
      s->nextarc=g->vertices[m].firstarc;
      g->vertices[m].firstarc=s;
      s=(struct arcnode *) malloc (sizeof(struct arcnode));
      s->adjvex=m;
      s->info=ifo;
      s->nextarc=g->vertices[n].firstarc;
      g->vertices[n].firstarc=s;

   }
}

int locate(algraph *x,char *z)
{
    int i;
    for(i=1;i<=x->vexnum;i++)
     {
        if(strcmp((x->vertices[i].data),z)==0)
         {
           return (i);
           break;
         }
     }
}

char *getvex(algraph *x,int v)
{
    char *j,tn[2];
    j=tn;
    if(v<0 || v>x->vexnum) printf("\nget error!\n");
    else
     {
        strcpy(j,x->vertices[v].data);
        return (j);
     }
}

void print(algraph *g)
{
    arcnode *p;
    int i,j,k;
    for(k=1;k<=g->vexnum;k++)
    {
        printf("%s->",g->vertices[k].data);
        p=g->vertices[k].firstarc;
        while(p!=NULL)
        {
            printf("%d p->info=%d\n",p->adjvex,p->info);
            p=p->nextarc;
            if(p!=NULL) printf("->");
        }
        printf("\n");
    }
}

mini_prim(algraph *g,char u[1])
{
    arcnode *p;
    int k,i,j,n;
    char tu;
    k=locate(g,u);
    printf("k=%d",k);
    p=g->vertices[k].firstarc;
    printf("p=%d",p->adjvex);
    j=1;
    for(i=1;i<=g->vexnum;i++)
     {
      min[i].lowcost=-1;
      printf("\nmin[%d].adj=%s min[%d].lowcost=%d\n",i,min[i].adj,i,min[i].lowcost);
     }
    while(p!=NULL)
        {
          if(j!=k)
           {
             strcpy(min[j].adj,u);
             printf("\nmin[%d].adj=%s\n",j,min[j].adj);
             min[j].lowcost=p->info;
             printf("\nmin[%d].lowcost=%d\n",j,min[j].lowcost);
             p=p->nextarc;
             j++;
           }
          else j++;
        }
    min[k].lowcost=0;
    printf("最小代价生成树的各条边为:\n");
    for(i=2;i<=g->vexnum;i++)
      {
        k=minimum(min,g);
                 //printf("\n'k=%d\n",k);
        printf("\n%s-%s\n",min[k].adj,g->vertices[k].data);
        min[k].lowcost=0;
                 printf("\n''k=%d\n",k);
        p=g->vertices[k].firstarc;
                 printf("\np->adjvex=%d g->vertices[k].data=%s k=%d\n",p->adjvex,g->vertices[k].data,k);
        j=1;
        while(j<=g->vexnum)
           {
            printf("\np->info=%d min[%d]=%d\n",p->info,p->adjvex,min[p->adjvex].lowcost);
            /*
if(min[p->adjvex].lowcost<0)
              {
                strcpy(min[p->adjvex].adj,g->vertices[p->adjvex].data);
                min[p->adjvex].lowcost=p->info;
                break;
              }*/
            if(p->info<min[p->adjvex].lowcost)
              {
                strcpy(min[p->adjvex].adj,g->vertices[p->adjvex].data);
                min[p->adjvex].lowcost=p->info;
                p=p->nextarc;
                j++;
              }
            else j++;
           }
        }
}

int minimum(struct closedge *SZ,algraph *x)
 { // 求closedge.lowcost的最小正值
   int i=1,j,k,min;
   while(SZ[i].lowcost==0)
   {
     printf("\nsz[%d]=%d\n",i,SZ[i].lowcost);
     i++;
   }
   min=SZ[i].lowcost; // 第一个不为0的值
   printf("\nisz[%d]=%d min=%d\n",i,SZ[i].lowcost,min);
   k=i;
   printf("k-start=%d\n",k);
   for(j=i+1;j<=x->vexnum;j++)
    {
      printf("j=%d",j);
      printf("\njsz[%d]=%d\n",j,SZ[j].lowcost);
      if(SZ[j].lowcost>0)
       {
         if(min>SZ[j].lowcost)
          {
            min=SZ[j].lowcost;
            k=j;
          }
       }
    }
   printf("k-end=%d\n",k);
   return k;
 }

main()
{
  algraph *G;
  char *u;
  int i;
  G=(struct algraph *) malloc (sizeof(struct algraph));
  creatal(G);
  print(G);
  printf("Input the start node:");
  scanf("%s",u);
  printf("%s",u);
  mini_prim(G,u);
}