c语言实现最小生成树算法.doc

最小生成树算法
C语言代码如下：
#include<stdio.h>
#include<windows.h>
#define TURE 999
typedef struct ArcNode
{ char vexs[10];
int edgs[10][10];
int n,e;
}MGraph;
struct edg{
int v1;
int v2;
int cost;
}A[10],B[10];
//创建图
void GreateMGraph(MGraph *G)
{ int i,j,k,weight,m,n;
int ch1,ch2;
char a,b;
printf("请输入顶点数和边数(格式如4):");
scanf("%d %d",&(G->n),&(G->e)); //输入顶点数,边数
for(i=0;i<G->n;i++)
{
getchar();
printf("请输入第%d个顶点:",i+1);
scanf("%c",&(G->vexs[i])); //输入¨顶点
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edgs[i][j]=0;
for(k=0;k<G->e;k++)
{
printf("请输入第%d条边的顶点权值(格式如¨i j):",k+1);
getchar();
scanf("%c %c %d",&a,&b,&weight);

m=0;n=0;
for( m=0;G->vexs[m]!=a;m++);
for( n=0;G->vexs[n]!=b;n++);
ch1=m;ch2=n;
G->edgs[ch1][ch2]=weight;G->edgs[ch2][ch1]=weight;

}
}

void prim(MGraph *G, int v)
{

int i,j,k,min;
struct
{ int adjvex;
int lowcost;
} closedge[10];
for (i=0;i<G->n;i++)
{
closedge[i].lowcost=G->edgs[v][i];
closedge[i].adjvex=v;
}
closedge[v].lowcost=TURE;
for (i=1;i<G->n;i++)
{
min=100;
for(j=0;j<G->n;j++)
if (closedge[j].lowcost!=TURE && closedge[j].lowcost!=0)
{
if (closedge[j].lowcost<min)
{
min=closedge[j].lowcost;
k=j;
}
}
printf("(%c,%c,%d) ", G->vexs[closedge[k].adjvex], G->vexs[k], min);
closedge[k].lowcost=TURE;
for (j=0;j<G->n;j++)

if (closedge[j].lowcost!=TURE)
if(G->edgs[k][j]<closedge[j].lowcost||closedge[j].lowcost==0 )
{
closedge[j].lowcost=G->edgs[k][j];
closedge[j].adjvex=k;
}
}
}

int main(void)
{
MGraph *G,a; char ch1;
G=&a;
printf("建立图的邻接矩阵\n");
GreateMGraph(G);
getchar();
ch1=1;
printf("\n");
printf("最小生成树 " );
printf("prim算法输出为a：");
prim(G,0);

system("pause");

}

运行结果截图：

在线编译成功；