#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINITY 30000
#define MAX_VERTEX_NUM 20
typedef struct
{int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
}Graph;
typedef struct CloseEdgel
{int adjvex;
int lowcost;
}ClosEdge;
void CreateGraph(Graph &);
void MiniSpanTree_PRIM(Graph ,int);
int minimum(ClosEdge[],int);
void main()
{Graph G;
char jx='y';
int u;
while(jx!='N'&&jx!='n')
{printf("请输入图的顶点和弧数，如8，9:");
scanf("%d,%d",&G.vexnum,&G.arcnum);
CreateGraph(G);
printf("请输入构造最小生成树的开始顶点:");
scanf("%d",&u);
MiniSpanTree_PRIM(G,u);
printf("最小代价生成树构造完毕，继续进行吗？(Y/N)");
scanf("&c",&jx);
}
}
void CreateGraph(Graph &G)
{
int i,j;
int start,end,weight;
for(i=1;i<=G.vexnum;i++)
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入每条边的两个关联顶点的编号和其上权值:\n");
for(i=1;i<G.arcnum;i++)
{scanf("%d,%d,%d",&start,&end,&weight);
G.arcs[start][end]=weight;
G.arcs[end][start]=weight;
}
}
void MiniSpanTree_PRIM(Graph G,int u)
{
ClosEdge closedge[MAX_VERTEX_NUM];
int i,j,k;
printf("最小代价生成树:\n");
for(j=1;j<=G.vexnum;j++)
if(j!=u)
{closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[u][j];
}
closedge[u].lowcost=0;
for(i=1;i<G.vexnum;i++)
{k=minimum(closedge,G.vexnum);
printf("%d,%d\n",closedge[k].adjvex,k);
closedge[k].lowcost=0;
for(j=1;j<=G.vexnum;j++)
if(G.arcs[k][j]<closedge[j].lowcost)
{closedge[j].adjvex=k;
closedge[j].lowcost=G.arcs[k][j];
}
}
}
int minimum(ClosEdge c1[],int vnum)
{
int i;
int w,p;
w=INFINITY;
for(i=1;i<=vnum;i++)
if(c1[i].lowcost!=0&&c1[i].lowcost<w)
{w=c1[i].lowcost;p=i;}
return p;
}
评论0