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

1构造n个城市连接的最小生成树一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)（1）代码：#include#include#define MaxVextexNum 30 /* 最大顶点数为30 */#define INFINITY 32767 /* 定义一个权值的最大值 */ typedef structint vexsMaxVextexNum ; /* 顶点表 */int arcsMaxVextexNumMaxVextexNum ; /* 邻接矩阵，即边表 */int n ,e ; /* 顶点数和边数 */MGraph ; /* MGragh是以邻接矩阵存储的图类型 */typedef struct int adjvertex ; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost ; /* 某顶点与已构造好的部分生成树的顶点之 间的最小权值 */ClosEdgeMaxVextexNum ; /* 用prim算法求最小生成树时的辅助数组 */void CreatGraph(MGraph *G) /* 建立有向图G的邻接矩阵存储 */ int i, j, k, w ;printf(请输入顶点数和边数n e:) ; scanf(%d%d ,&(G-n) ,&(G-e) ;/* 输入顶点数和边数 */printf(n请输顶点字符信息(共%d个)：, G-n) ; for (i=0 ;in ;i+) scanf(%d ,&(G-vexsi) ; /* 输入顶点信息，建立顶点表 */ for (i=0 ;in ;i+) for (j=0 ;jn ;j+) if(i = j)G-arcsij = 0 ;elseG-arcsij = INFINITY ; /* 初始化邻接矩阵 32767为无穷大*/printf(n请输入边对应的顶点序号(共%d对)，以及权值:n,G-e) ; for (k=0 ;ke ;k+)scanf(%d%d%d ,&i ,&j ,&w) ; /*输入e条边，建立邻接矩阵 */ G-arcsij = w ;/* 若加入G-edgesji=1，则为无向图的邻接矩阵*/ G-arcsji = w ;printf(此连邻接矩阵为（32767为无穷大）：n) ;for(i=0 ;in ;i+)for(j=0 ;jn ;j+)printf(%8d, G-arcsij) ;printf(n) ; void MiniSpanTree_PRIM(MGraph G,int u,ClosEdge closedge)/* 从第u个顶点出发构造图G的最小生成树，最小生成树顶点信息存放在数组closedge中*/int i ,j ,w ,k ,cost = 0 ; for(i=0 ;iG.n ;i+) /* 辅助数组初始化 */ if(i != u) closedgei.adjvertex = u ; closedgei.lowcost = G.arcsui ; closedgeu.lowcost = 0 ; /* 初始，U=u */ for(i=0 ;iG.n-1 ;i+) /* 选择其余的G.n-1个顶点 */ w=INFINITY ;for(j=0 ;jG.n ;j+) /* 在辅助数组closedge中选择权值最小的顶点*/ if(closedgej.lowcost!=0 & closedgej.lowcostw) w=closedgej.lowcost ; k=j ; /* 求出生成树的下一个顶点k */ closedgek.lowcost=0 ; /* 第k顶点并入U集 */for(j=0 ;jG.n ;j+) /* 新顶点并入U后，修改辅助数组*/ if(G.arcskjclosedgej.lowcost) closedgej.adjvertex=k ; closedgej.lowcost=G.arcskj ; printf(n最小生成树中包括的城市间的道路:n) ; for(i=0; i%d,%dn, i ,closedgei.adjvertex ,G.arcsiclosedgei.adjvertex) ; cost=cost+G.arcsiclosedgei.adjvertex ; printf(n最小生成树的代价为:%dnn, cost) ;int main()int t ;MGraph G;ClosEdge closedge ; CreatGraph( &G ) ;printf(请输入源点：) ;scanf(%d, &t) ; MiniSpanTree_PRIM(G ,t ,closedge) ;return 1 ;结果：（2）各模块功能说明：CreatGraph：，创建邻接矩阵，用邻接矩阵表示城市间的距离网，邻若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。然后在屏幕上显示得到的最小生成树中包括了哪些城市间的道路 MiniSpanTree_PRIM：用Prim算法建立最小生成树，并计算得到的最小生成树的代价主函数：调用各函数，并输出最后结果3、 总结：在做课程设计的时候，我们要先搞清楚原理，再考虑如何去实现！对于城市的最小生成树问题，让我认识到图能够在计算机中存在，首先要捕捉它有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也是说明了想要把生活中的信息转化成到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点与顶点之间的联系，图分为有向图和无向图，而无向图又是有向图在权值双