最小生成树问题中北大学数据结构课程设计 

int i ;

printf(\请输入城市的数量及城市间的路径数目\\n\ scanf(\ for(i=0;ivexnum;i++) {/* 建立顶点表 */

printf(\请输入第%d个城市的名称\\n\

scanf(\读入顶点信息 */ G->adjlist[i].firstarc=NULL;/* 边表置为空表 */ G->adjlist[i].bianhao = i; }

printf(\每个城市所对应的序号为\\n\ for(i = 0;ivexnum;i++) {

printf(\序号：%d--->城

市：%s\\n\注意此处的& }

return OK; }

Status PrintALGraph(ALGraph *G){ int i,end,begin,weight; ANode *s;

for(i=0;ivexnum;i++){/* 建立顶点表 */ printf(\ s = G->adjlist[i].firstarc; while(s!=NULL) {

printf(\

\ s = s->nextarc;

5

}

printf(\ }

return OK; }

void CreateALGraph(ALGraph *G) {

int i,j,k,weight; ANode *s; InitALGraph(G);

for(k=0;k< G-> arcnum;k++){ /* 建立边表 */

printf(\请输入第%d条边的两个城市的编号及路径的架设费用:\ scanf(\ scanf(\

scanf( \读入边(vi，vj)的顶点对序号 */ s=(ANode*)malloc(sizeof(ANode)); /* 生成边表结点 */ if(!s) {

printf(\申请空间失败!\\n\ exit(OVERFLOW); }

s->begin=j; /* 邻接点序号为j */ s->end = i; s->weight = weight;

s->nextarc= G->adjlist[i].firstarc; G->adjlist[i].firstarc=s; /*将新结点*s插入顶点vi的边表头部 */

s=(ANode*)malloc(sizeof(ANode)); if(!s) {

printf(\申请空间失败!\\n\

6

exit(OVERFLOW); }

s->begin=i; /* 邻接点序号为i */ s->end=j; s->weight=weight;

s->nextarc=G->adjlist[j].firstarc;

G->adjlist[j].firstarc=s; /* 将新结点*s插入顶点vj的边表头部 }

PrintALGraph(G); }/* CreateALGraph */

Status PrintMGraph(MGraph *G){ int a; int i,j;

printf(\邻接矩阵表示法为：\\n\ printf(\

for(i=0;ivexnum;++i) printf(\ printf(\

for ( i=0; ivexnum; i++) {

printf(\ for ( j=0; jvexnum; j++) {

printf(\ }

printf(\ }

return OK; }

7

*/

图二

Status InitMGraph(MGraph *G){ int i,j;

printf(\请输入城市的数量及城市间的路径数目：\\n\ scanf(\

printf(\请依次输入城市的名称，字符串类型\\n\ for(i=0;ivexnum;++i) {

/*构造顶点向量*/

scanf(\ }

for(i=0;ivexnum;++i) /*初始化邻接矩阵*/

for(j=0;jvexnum;++j) G->arcs[i][j].adj=INFINITY; return OK; }

Status CreateMGraph(MGraph *G)

{/*采用数组（邻接矩阵）表示法，构造无向网G*/

8

int i,j,k,weight,IncInfo; VertexType va,vb; InitMGraph(G);

for(k=0;karcnum;++k)

{ printf(\请输入第%d条路径的起点城市和终点城市的名称及路径的架设费用\\n\ scanf(\ i=LocateVex(G,va); j=LocateVex(G,vb); G->arcs[i][j].adj=weight; G->arcs[j][i].adj=weight; }

PrintMGraph(G); return OK; }

typedef struct MINSIZE

{//记录从顶点集U到V-U的代价最小的边的辅助数组定义* VertexType adjvex; VRType lowcost;

}minside[MAX_VERTEX_NUM];

Status mininum(minside closedge,MGraph *G) {/*求closedege,lowcost的最小正值*/ int i=0,j,k,min;

while(!closedge[i].lowcost) i++;

min=closedge[i].lowcost; k=i;

for(j=i+1;jvexnum;j++) if(closedge[j].lowcost>0) if(min>closedge[j].lowcost) {

9