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

#define MaxSize 20
#define MAX     10000

typedef char VertexType;

typedef struct Graph{
    VertexType ver[MaxSize];
    int edg[MaxSize][MaxSize];
}Graph;

void CreateGraph(Graph *g){
    int i=0;
    int j=0;
    int VertexNum;
    VertexType Ver;
    printf("请输入图的顶点：\n");
    while('\n'!=(Ver=getchar()))
        g->ver[i++]=Ver;
    g->ver[i]='\0';
    VertexNum=strlen(g->ver);
    printf("请输入相应的邻接矩阵：\n");
    for(i=0;i<VertexNum;i++)
        for(j=0;j<VertexNum;j++)
            scanf("%d",&g->edg[i][j]);
}

void PrintfGraph(Graph g){
    int i=0;
    int j=0;
    int VertexNum=strlen(g.ver);
    printf("图的邻接矩阵为：\n");
    for(i=0;i<VertexNum;i++)
        printf("%c",g.ver[i]);
    printf("\n");
    for(i=0;i<VertexNum;i++){
        printf("%c ",g.ver[i]);
        for(j=0;j<VertexNum;j++)
            printf("%d ",g.edg[i][j]);
        printf("\n");
    }
}

int CalVerNum(Graph g){
    return strlen(g.ver);
}

void SetWeight(Graph *g){
    int i=0;
    int j=0;
    for(i=0;i<CalVerNum(*g);i++)
        for(j=0;j<CalVerNum(*g);j++)
            if(0==g->edg[i][j])
                g->edg[i][j]=MAX;
}
void prim(Graph g,int VerNum,int *parent){
    int i=0;
    int j=0;
    int k=0;
    int lowcost[MaxSize];
    int closest[MaxSize];
    int used[MaxSize];
    int min;
    for(i=0;i<VerNum;i++){
        lowcost[i]=g.edg[0][i];
        closest[i]=0;
        used[i]=0;
        parent[i]=-1;
    }
    used[0]=1;
    for(i=0;i<VerNum-1;i++){
        j=0;
        min=MAX;
        for(k=1;k<VerNum;k++){
            if((0==used[k])&&(lowcost[k]<min)){
                min=lowcost[k];
                j=k;
            }
        }
        parent[j]=closest[j];
        used[j]=1;
        for(k=0;k<VerNum;k++){
            if((0==used[k])&&(g.edg[k][j]<lowcost[k])){
                lowcost[k]=g.edg[k][j];
                closest[k]=j;
            }
        }
    }

}

void PrintMST(Graph g,int *parent){
    int VerNum=CalVerNum(g);
    int weight=0;
    printf("MST的边为：\n");
    int i=0;
    for(i=1;i<VerNum;i++){
        printf("%c--%c\n",g.ver[parent[i]],g.ver[i]);
        weight+=g.edg[parent[i]][i];
    }
    printf("MST的权值为:%d\n",weight);
}

int main(void)
{
    Graph g;
    int parent[20];
    CreateGraph(&g);
    PrintfGraph(g);
    SetWeight(&g);
    prim(g,CalVerNum(g),parent);
    PrintMST(g,parent);
    return 0;
}