构造n个城市连接的最小生成树.docx

:..,用Prim算法或Kruskal算法建立最小生成树,计算得到的最小生成树的代价。基本要求:1)城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市,10条边)(1)代码:#include<>#include<>#defineMaxVextexNum30/*#defineINFINITY32767/*最大顶点数为30*/定义一个权值的最大值*/typedefstruct{intvexs[MaxVextexNum];/*顶点表*/intarcs[MaxVextexNum][MaxVextexNum]; /*邻接矩阵,即边表*/intn,e;/*顶点数和边数*/}MGraph;/*MGragh是以邻接矩阵存储的图类型*/点*/typedefstruct{intadjvertex;/*某顶点与已构造好的部分生成树的顶点之间权值最小的顶intlowcost;/* 某顶点与已构造好的部分生成树的顶点之 间的最小权值*/}ClosEdge[MaxVextexNum];/*用prim算法求最小生成树时的辅助数组*/建立有向图G的邻接矩阵存储*/voidCreatGraph(MGraph*G)/*{inti,j,k,w;printf("请输入顶点数和边数ne:");scanf("%d%d",&(G->n),&(G->e));/*输入顶点数和边数*/printf("\n 请输顶点字符信息 (共%d个):",G->n);for(i=0;i<G->n;i++){scanf("%d",&(G->vexs[i]));/* 输入顶点信息,建立顶点表*/}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++){if(i==j){G->arcs[i][j]=0;}elseG->arcs[i][j]=INFINITY;}/*初始化邻接矩阵32767为无穷大*/printf("\n 请输入边<Vi,Vj>对应的顶点序号(共%4对),以及权值:\n",G->e);for(k=0;k<G->e;k++){scanf("%d%d%d",&i,&j,&w);/* 输入e条边,建立邻接矩阵*/G->arcs[i][j]=w;/* 若加入G->edges[j][i]=1,则为无向图的邻接矩阵*/G->arcs[j][i]=w;}printf("此连邻接矩阵为(32767为无穷大):\n");for(i=0;i<G->n;i++){for(j=0;j<G->n;j++)printf("%8d",G->arcs[i][j]);printf("\n");}}voidMiniSpanTree_PRIM(MGraphG,intu,ClosEdgeclosedge){/*从第u个顶点出发构造图 G的最小生成树,最小生成树顶点信息存放在数组closedge中*/inti,j,w,k,cost=0;for(i=0;i<;i++)/* 辅助数组初始化*/if(i!=u)closedge[i].adjvertex=u;closedge[i].lowcost=[u][i];初始,U={u}*/closedge[u].lowcost=0;/*for(i=0;i<;i++)/*选择其余的个顶点*/{w=INFINITY;for(j=0;j<;j++)/*在辅助数组closedge中选择权值最小的顶点*/if(closedge[j].lowcost!=0&&closedge[j].lowcost<w){w=closedge[j].lowcost;k=j;}/*求出生成树的下一个顶点k*/closedge[k].lowcost=0;/*第k顶点并入U集*/for(j=0;j<;j++)/* 新顶点并入U后,修改辅助数组*/if[k][j]<closedge[j].lowcost){closedge[j].adjvertex=k;closedge[j].lowcost=[k][j];}}printf("\n最小生成树中包括的城市间的道路:\n");for(i=0;i<;i++)/*打印最小生成树的各条边*/if(i!=u){printf("%d->%d,%d\n",i,closedge[i].adjvertex,[i][closedge[i].adjvertex]);cost=cost+[i][closed