用c写最小生成树的算法

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

#define EMPTY_NUM 80
#define MAX_VERTEX_NUM 20

typedef char Vertex_Type[5];

typedef struct AdjMatrix
{
    int weight;
}Adj_Matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
    Vertex_Type vertexs_vectors[MAX_VERTEX_NUM];
    Adj_Matrix arcs;
    int arc_num;
    int vertex_num;
}AMGraph;

struct
{
    Vertex_Type adj_vertex;
    int        lowcost;
}closedge[MAX_VERTEX_NUM];

void Init_UDN( AMGraph &G )
{
    printf("输入图的弧的数量:");
    scanf("%d", &G.arc_num);
    printf("输入图的顶点数:");
    scanf("%d", &G.vertex_num);
   
    int j, i;
    printf("输入顶点向量:");
    for( i=0; i<G.vertex_num; ++i )
        scanf("%s", G.vertexs_vectors[i]);
    for( i=0; i<G.vertex_num; ++i )
        for( j=0; j<G.vertex_num; ++j )
            G.arcs[i][j].weight = G.arcs[j][i].weight = EMPTY_NUM;
}

int Get_Vertex_Location( AMGraph G, Vertex_Type v )
{
    int i;
    for( i=0; i<G.vertex_num; ++i )
        if( strcmp(G.vertexs_vectors[i], v) == 0 )
            break;
    return i;
}

void Create_UDN( AMGraph &G )
{
    Init_UDN( G );
   
    Vertex_Type v1, v2;
    int i, v1_site, v2_site, w;

    printf("输入图的弧和权值(v1 -- v2 ,3):\n");
    for( i=0; i<G.arc_num; ++i )
    {
        scanf("%s %*s %s ,%d", v1, v2, &w);
        v1_site = Get_Vertex_Location( G, v1 );
        v2_site = Get_Vertex_Location( G, v2 );
        G.arcs[v1_site][v2_site].weight = G.arcs[v2_site][v1_site].weight = w;
    }
}

void Print_Graph( AMGraph G )
{
    for(int i=0; i<G.vertex_num; ++i )
    {
        for(int j=0; j<G.vertex_num; ++j )
            printf(" %d ", G.arcs[i][j].weight);
        printf("\n");
    }
}

int Min_Num( AMGraph G )
{
    int j = -1;
    for( int i=0; i<G.vertex_num; ++i )
    {
        if( closedge[i].lowcost > 0 && j == -1 )
            j = i;
        if( closedge[i].lowcost> 0 && j != -1 && closedge[j].lowcost > closedge[i].lowcost )
            j = i;
    }
    return j;
}

void MininSpanTree_Prim( AMGraph G, Vertex_Type V )
{
    int k = Get_Vertex_Location( G, V );

    for( int j=0; j<G.vertex_num; ++j )
    {
        closedge[j].lowcost = G.arcs[k][j].weight;
        strcpy( closedge[j].adj_vertex, V );
    }
    closedge[k].lowcost = 0;
    for( int i=1; i<G.vertex_num; ++i )
    {
        k = Min_Num( G );
        closedge[k].lowcost = 0;

        printf("%s--%s ", closedge[k].adj_vertex, G.vertexs_vectors[k] );
        for( int j = 0; j<G.vertex_num; ++j )
            if( closedge[j].lowcost > G.arcs[k][j].weight )
            {
                closedge[j].lowcost = G.arcs[k][j].weight;
                strcpy( closedge[j].adj_vertex, G.vertexs_vectors[k] );
            }
    }
}

int main()
{
    AMGraph G;
    Vertex_Type v;

    Create_UDN( G );

    Print_Graph( G );

    printf("输入从哪个点开始:");
    scanf("%s", v);
    MininSpanTree_Prim( G, v );
    printf("\n");

    return 0;
}
 

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
    int *array;//表示邻接矩阵的二维数组
    int vexnum;//顶点数
}Magraph;
typedef struct//辅助数组
{
    int adjvex;
    int lowcost;
}array;
array *closedge;
void CreatGraph(Magraph *G)/////创建网
{
    int a,n;
    int i,j,flag=0;
    printf("请输入你想创建的邻接矩矩阵的行列数(即顶点数):\n");//创建网的邻接矩矩阵(n行n列)
    scanf("%d",&n);
    G->array=(int *)malloc(n*n*sizeof(int));
    G->vexnum=n;
    printf("请输入一个%d行%d列的关于网的邻接矩阵:\n",n,n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&a);
            *(G->array+i*n+j)=a;
        }   
}
void PrintGraph(Magraph G)//打印输出网的信息
{
    int i,j;
    printf("网的相关信息如下:\n");
    printf("(1)网的顶点数为%d.\n",G.vexnum);
    printf("(2)输出网的邻接矩阵表示:\n");
    for(i=0;i<G.vexnum;i++)
    {
        for(j=0;j<G.vexnum;j++)
            printf("%5d ",*(G.array+i*G.vexnum+j));
        printf("\n");
    }
}
int minimum(array *closedge,int n)//确定不为0的最小closedge[i].lowcost的下标
{
    int min,min_order,i;
    for(i=2;i<=n;i++)//1.将第一个不为0的值设为min,他的下标设为min_order
    {
        if(closedge[i].lowcost!=0)
        {
            min=closedge[i].lowcost;
            min_order=i;
            break;
        }
    }
    for(i=i+1;i<=n;i++)
    {
        if((closedge[i].lowcost<min)&&(closedge[i].lowcost>0))
        {
            min=closedge[i].lowcost;
            min_order=i;
        }
    }
    return(min_order);
}
void MiniSpanTree(Magraph G)
{
    int i,j,k;
    k=1;//从第一个顶点开始构建最小生成树
    closedge=(array*)malloc((G.vexnum+1)*sizeof(array));
    for(j=1;j<=G.vexnum;j++)//初始化closedge辅助数组
    {
        if(j!=k)
        {
            closedge[j].adjvex=k;
            closedge[j].lowcost=*(G.array+(k-1)*G.vexnum+j-1);
        }
    }
    closedge[k].lowcost=0;
    printf("所得最小生成树的边依次为:\n");
    for(i=1;i<G.vexnum;i++)
    {
        k=minimum(closedge,G.vexnum+1);//确定不为0的最小closedge[i].lowcost的下标
        printf("(%d,%d) ",closedge[k].adjvex,k);//输出生成树的边
        closedge[k].lowcost=0;//将该顶点并入U中
        for(j=1;j<=G.vexnum;j++)//重新找最小边
        {
            if(*(G.array+(k-1)*G.vexnum+j-1)<closedge[j].lowcost)
            {
                closedge[j].adjvex=k;
                closedge[j].lowcost=*(G.array+(k-1)*G.vexnum+j-1);
            }
        }
    }
    printf("\n");
}
void main()
{
    Magraph G;
    CreatGraph(&G);
    PrintGraph(G);
    MiniSpanTree(G);
}