文档介绍：最小生成树课程设计
学 院、系 专 业： 学生姓名 设计题目
中北大学
数据结构与算法课程设计
说明书
软件学院
软件工程
xx 学 号： xxx
最小生成树问题
2013 年12月9日-2013 年 12 月20
ance of scanf("%s%s%d",x,y,&c); 间的距离(图中边的起点和终点及权值) */
/*
of
/*
least
输入
%d
输入
/* 初始化
a road :"); /* 输入城市
a=locatedvex(*g,x);
b=locatedvex(*g,y); while(a==-1||b==-1){ printf("the name of the city is wrong!\n"); printf("input the distance of a road
again :");
scanf("%s%s%d",x,y,&c);
a=locatedvex(*g,x);
b=locatedvex(*g,y);
}
g->arcs[a][b].adj=c; g->arcs[b][a]=g->arcs[a][b];
} void print(mgraph g) /*输出用邻 接矩阵构造的n个城市间距离网g*/
int i,j;
for (i=0;i<;i++)
{for(j=0;j<;j++)
printf("%-4d
",[i][j].adj);
printf("\n");
}
}
void minispantree(mgraph g,vertextype
x){ /*从第k个顶点出发构造图g的最小生
成树 */
int i,j,t,k,sum=0; k=locatedvex(g,x); for(j=0;j<;j++)
/*辅助数组初始化*/
if(j!=k)
{ [j].lowcost=[k][j].adj;
strcpy([j].adjvex,x);
}
[k].lowcost=0;
/* 初始，U={u} */
for(i=1;i<;i++){
/*选择其余的G->vexnum-1个顶点*/ k=min(g);
/*求出生成树的下一个顶点 */
printf("(%s,%s) %d\n", ge[k].adjvex,[k],[k].lowc ost); /*输出生成树的边和权值 */
sum+=[k].lowcost;
/*计算最小生成树的代价*/
[k].lowcost=0;
/*第k顶点并入U集*/
/*
for(t=0;t<;t++)
新顶点并入U后，修改辅助数组*/
if([k][t].adj<[t].lowcost
){
strcpy([t].adjvex,g
vexs[k]);
[t].lowcost=[k
][t].adj;
}
shortest distance
/*输出最小生成树
/* 在辅助数组
} printf("The is %d\n",sum); 的代价*/ } int min(mgraph g){
g. closedge[i]中选择权值最小的顶点，并返回
其位置 */
int i,a=0,min;
min=maxnum;
for(i=1;i<;i++)
if([i].lowcost<min&&
[i].lowcost!=0){
a=i;
min=[i].lowcost;
}
return a;
}
int locatedvex(mgraph g,vertextype u){ /*
确定任一城市在距离网g中的位置*/
int i;
for(i=0;i<;i++) if(strcmp(u,[i])==0) return i;
return -1;
}
int main()
{ mgraph g; vertextype u; in