最小代价树.c

数据库结构课本中二叉树中求最小代价生成树

#include<stdio.h>
#define MAX 100
struct Closedge{
        Vertex adjvex;
        int lowcost;
}closedge[MAX];
typedef struct ArcCell{
        int adj;
        int * info;
}AdjMatrix[MAX][MAX];
typedef struct{
        Vertex vexs[MAX];
        AdjMatrix arcs;
        int vexnum,arcnum;
}MGraph;
void CreatGraph(void);
void MiniSpanTree_PRIM(void);
int Minimum(void);
int vexnum,arcnum;
MGraph G;
int main()
{
    int i;
    printf("请输入图的顶点数和弧数(以空格隔开):\n");
    scanf("%d %d",&vexnum,&arcnum);
    for (i=0;i<vexnum;i++)
        scanf("%s",)
    printf("请输入图的邻接矩阵(若两节点之间无弧，用10000表示):\n");
    CreatGraph();
    MiniSpanTree_PRIM();
    
    system("pause");
    return 0;
}
    
void CreatGraph(void)
{
     int i, j;
     
     G.vexnum = vexnum;
     G.arcnum = arcnum; 
     for (i=0; i<vexnum; i++)
         G.vexs[i] = i + 1;
     for (i=0; i<G.vexnum; i++)
         for (j=0; j<G.vexnum; j++)
         {
             scanf("%d",&G.arcs[i][j].adj);
             G.arcs[i][j].info = NULL;
         }
} 
void MiniSpanTree_PRIM(void)
{
     int k,j,i;
     
     k = 0;
     for (j=0; j<G.vexnum; j++)
     {
         closedge[j].adjvex = k + 1;
         closedge[j].lowcost = G.arcs[k][j].adj;
     }
     closedge[k].lowcost = 0;
     printf("最小生成树是:\n"); 
     for (i=1; i<G.vexnum; i++)
     {
         k = Minimum();
         printf("%d->%d ",closedge[k].adjvex,G.vexs[k]);
         closedge[k].lowcost = 0;
         for (j=0; j<G.vexnum; j++)
             if (G.arcs[k][j].adj < closedge[j].lowcost)
             {
                closedge[j].adjvex = G.vexs[k];
                closedge[j].lowcost = G.arcs[k][j].adj;
             }
     }   
}
int Minimum(void)
{
    int k,i;
    int Least = 100000;
    
    for (i=0; i<vexnum; i++)
        if ((closedge[i].lowcost!=0) && (closedge[i].lowcost < Least))
        {
           Least = closedge[i].lowcost;
           k = i;
        }
    return k;
}