最小生成树问题.doc

中北大学数据结构与算法课程设计说明书 学院、系:软件学院专业:软件工程学生姓名:xx学号:xxx设计题目:最小生成树问题起迄日期:20年12月9日-20年12月20日指导教师:   20年12月20日需求分析设计内容:给定一个地区的n个城市间的距离网,用prim算法或kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求: (1)城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价; (2)表示城市间距离网的邻接矩阵(要求至少6个城市,10条边); (3)最小生成树中包括的边及其权值,并显示得到的最小生成树的代价。2本设计所采用的数据结构本程序设计所采用的数据结构为图。3设计思想普里姆算法4核心代码intmain()//主函数{mgraphg;vertextypeu;intk;createUDN(&g);/*生成邻接矩阵结构的图*/printf("\nThegraphis:\n");print(g);/*输出邻接矩阵*/printf("inputthecityyouwanttostart:");scanf("%s",u);/*输入最小生成树的起点*/k=locatedvex(g,u);while(k==-1){printf("thenameofthecityiswrong!\n");printf("inputthecityyouwanttostartagain:");scanf("%s",u);k=locatedvex(g,u);}minispantree(g,u);/*普里姆算法求最小生成树*/}4代码#include""#include""#definemaxnum20/*图的最大顶点数*/#defineINFINITY1000/*定义一个权值的最大值*/typedefcharvertextype[20];/*定义城市名称*/ell{intadj;/*弧的权值*/int*info;/*弧上相关信息的指针*/}ell;typedefstructarray{vertextypeadjvex;/*顶点的邻接点*/intlowcost;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/}array;typedefstruct{ vertextypevexs[maxnum];/*顶点向量*/ ellarcs[maxnum][maxnum];/*邻接矩阵*/ intvexnum,um;/*图的顶点个数和弧个数*/ arrayclosedge[maxnum];/*用普里姆算法求最小生成树时的辅助数组*/}mgraph;voidcreateUDN(mgraph*g){/*用邻接矩阵构造n个城市间的距离网g*/inti,j,m,n,k,a,b,c;vertextypex,y;printf("inputthenumberofcities(atleast6cities):");scanf("%d",&g->vexnum);/*输入城市的个数(图的顶点数)*/printf("inputthenumberofroads(atleast10road