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

1．构造n个城市连接的最小生成树一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1)城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)（1）代码：#includestdio.h#includestdlib.h#defineMaxVextexNum30/*最大顶点数为30*/#defineINFINITY32767/*定义一个权值的最大值*/typedefstruct{intvexs[MaxVextexNum];/*顶点表*/intarcs[MaxVextexNum][MaxVextexNum];/*邻接矩阵，即边表*/intn,e;/*顶点数和边数*/}MGraph;/*MGragh是以邻接矩阵存储的图类型*/typedefstruct{intadjvertex;/*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/intlowcost;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/}ClosEdge[MaxVextexNum];/*用prim算法求最小生成树时的辅助数组*/voidCreatGraph(MGraph*G)/*建立有向图G的邻接矩阵存储*/{inti,j,k,w;printf(请输入顶点数和边数ne:);scanf(%d%d,&(G-n),&(G-e));/*输入顶点数和边数*/printf(\n请输顶点字符信息(共%d个)：,G-n);for(i=0;iG-n;i++){scanf(%d,&(G-vexs[i]));/*输入顶点信息，建立顶点表*/}for(i=0;iG-n;i++)for(j=0;jG-n;j++){if(i==j){G-arcs[i][j]=0;}elseG-arcs[i][j]=INFINITY;}/*初始化邻接矩阵32767为无穷大*/printf(\n请输入边Vi,Vj对应的顶点序号(共%d对)，以及权值:\n,G-e);for(k=0;kG-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;iG-n;i++){for(j=0;jG-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;iG.n;i++)/*辅助数组初始化*/if(i!=u){closedge[i].adjvertex=u;closedge[i].lowcost=G.arcs[u][i];}closedge[u].lowcost=0;/*初始，U={u}*/for(i=0;iG.n-1;i++)/*选择其余的G.n-1个顶点*/{w=INFINITY;for(j=0;jG.n;j++)/*在辅助数组closedge中选择权值最小的顶点*/if(closedge[j].lowcost!=0&&closedge[j].lowcostw){w=closedge[j].lowcost;k=j;}/*求出生成树的下一个顶点k*/closedge[k].lowcost=0;/*第k顶点并入U集*/for(j=0;jG.n;j++)/*新顶点并入U后，修改辅助数组*/if(G.arcs[k][j]closedge[j].lowcost){closedge[j].adjvertex=k;closedge[j].lowcost=G.arcs[k][j];}}printf(\n最小生成树中包括的城市间的道路:\n);for(i=0;iG.n;i++)/*打印最小生成树的各条边*/if(i!=u){printf(%d-%d,%d\n,i,closedge[i].adjvertex,G.arcs[i][closedge[i].adjvertex]);cost=cost+G.arcs[i][closedge[i].adjvertex];}printf(\n最小生成树的代价为:%d\n\n,cost);}intmain(){intt;MGraphG;ClosEdgeclosedge;CreatGraph(&G);printf(请输入源点：);scanf(%d,&t);MiniSpanTree_PRIM(G,t,closedge);return1;}结果：（2）各模块功能说明：①CreatGraph：，创建邻接矩阵，用邻接矩阵表示城市间的距离网，邻若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。然后在屏幕上显示得到的最小生成树中包括了哪些城市间的道路②MiniSpanTree_PRIM：用Prim算法建立最小生成树，并计算得到的最小生成树的代价③主函数：调用各函数，并输出最后结果3、总结：在做课程设计的时候，我们要先搞清楚原理，再考虑如何去实现！对于城市的最小生成树问题，让我认识到图能够在计算机中存在，首先要捕捉它有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也是说明了想要把生活中的信息转化成到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点与顶点之间的联系，图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例。这次课程设计让我认识到对于一段代码，我们不仅要考虑它的可行性，更应该考虑它的算法复杂度，运行效率。做同一件事，一万个人有一万种做法，换而言之，一万个人写一段代码实现同一个功能可以得到一万段代码。由此，我们可以看出做一件事要精益求精，多加斟酌。