最小生成树普利姆算法c语言实现__Prim

为方便，本程序中所用图结点及边在main函数中直接定义

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

#define MAXVEX 5
#define INFINITY 65535   // 权值为65535以为两个结点之间没有连接的边，即为我们通常所说的∞
struct MGraph{ //邻接矩阵表示图
int numVertexes; //结点数
char *vex;  //结点
int **arc;  //边
};

void MiniSpanTree_Prim(MGraph *G)
{
int min,i,j,k;
int adjvex[MAXVEX];
int lowcost[MAXVEX];

lowcost[0]=0;
adjvex[0]=0;

for(i=1;i<G->numVertexes;++i)
{
lowcost[i]=G->arc[0][i];
adjvex[i]=0;
}

for(i=1;i<G->numVertexes;++i)
{
min=INFINITY;
j=1;
k=0;

while(j<G->numVertexes)
{
if(lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
++j;
}

printf("{%d,%d}",adjvex[k],k);
lowcost[k]=0;

for(j=1;j<G->numVertexes;++j)
{
if(lowcost[j]!=0 && G->arc[k][j]<lowcost[j])
{
lowcost[j]=G->arc[k][j];
adjvex[j]=k;
}
}
}
}

void main()
{
MGraph *my_g=(struct MGraph*)malloc(sizeof(struct MGraph));
int i,j;
int t=0;
char c='A';
my_g->numVertexes=5;
my_g->vex=(char*)malloc(sizeof(char)*my_g->numVertexes);
if(!my_g->vex) return;
for(i=0;i<my_g->numVertexes;++i)  //一维数组(图中各结点)初始化{A,B,C,D,E}
my_g->vex[i]=c++;
my_g->arc=(int**)malloc(sizeof(int*)*my_g->numVertexes);
if(!my_g->arc)  return;
int **temp=my_g->arc;
while(t<my_g->numVertexes)  //二维数组(各边的权值)初始化
{
*temp=(int*)malloc(sizeof(int)*my_g->numVertexes);
if(!*temp)  return;
++temp;
++t;
}
for(i=0;i<my_g->numVertexes;++i)
for(j=0;j<my_g->numVertexes;++j)
my_g->arc[i][j]=-1;
my_g->arc[0][1]=3;  my_g->arc[0][2]=2;  my_g->arc[0][3]=9;  my_g->arc[0][4]=INFINITY;  // 无向图的权值二维数组为对称矩阵
my_g->arc[1][2]=INFINITY;  my_g->arc[1][3]=4;  my_g->arc[1][4]=5;
my_g->arc[2][3]=INFINITY;  my_g->arc[2][4]=INFINITY;
my_g->arc[3][4]=7;
for(i=0;i<my_g->numVertexes;++i)
for(j=0;j<=i;++j)
{
if(i==j)
{
my_g->arc[i][j]=0;
continue;
}
my_g->arc[i][j]=my_g->arc[j][i];
}
    for(i=0;i<my_g->numVertexes;++i)  //二维数组表示图中各结点间连接边的weight
{
for(j=0;j<my_g->numVertexes;++j)
printf("%5d  ",my_g->arc[i][j]);
printf("\n");
}
printf("\n\n");

MiniSpanTree_Prim(my_g);
}

本程序所用图的结点，即my_g->vex[5]=={A,B,C,D,E}.

但是在最小生成树的建立过程中，为方便起见用了编号表示结点，即：将{A,B,C,D,E}  编号为  {0,1,2,3,4}

所以程序运行结果 {0,2} {0,1} {1,3} {1,4}  意思就是  {A,C} {A,B} {B,D} {B,E}   // 也就是将printf时的  { adjvex[k] , k } 转换为 { G->vex[adjvec[k]] , G->vex[k] }