构造可以使n个城市连接的最小生成树互联网

1、互联网 2数据结构课程设计报告设计题目：构造可以使设计题目：构造可以使 n n 个城市连接的最小生成个城市连接的最小生成树树姓名：姓名： 学号：学号：专业：物联网工程（嵌入式培养）专业：物联网工程（嵌入式培养）院系：计算机技术与科学学院院系：计算机技术与科学学院班级：班级：14051405指导教师：指导教师： 互联网 220162016 年年 0101 月月 0909 日日 互联网 2摘要本次课程设计的要求是给定一个地区的本次课程设计的要求是给定一个地区的 n n 个城市间的距离个城市间的距离网，用网，用 primprim 算法建立最小生成树，并计算得到的最小生成算法建立最小生成树，并计算得到

2、的最小生成树的代价。将该地区的城市用顶点表示，城市间的公路用树的代价。将该地区的城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，最终这个问题可以归边表示，公路的长度作为边的权值，最终这个问题可以归结为网图中，求顶点结为网图中，求顶点 a a 到顶点到顶点 b b 的所有路径中，边的权值的所有路径中，边的权值之和最少的那条路径。之和最少的那条路径。关键词：关键词：最小生成树最小生成树 primprim 算法算法 c+c+语言源程序语言源程序互联网 2abstractthethe currcurriculumiculum designdesign requirementsrequir

3、ements isis givengiven a a regionregion n n city,city, thethe distancedistance betweenbetween thethe netnet withwith thethe primprim algorithmalgorithm toto establishestablish minimumminimum spanningspanning tree,tree, andand calculatedcalculated thethe priceprice ofof minimumminimum spanningspannin

4、g tree.tree. citiescities inin thethe regionregion withwith vertexvertex said,said, betweenbetween highwayhighway inin thethe citycity edge,edge, saidsaid thethe lengthlength ofof thethe roadroad asas thethe edgeedge ofof thethe rightright values,values, finallyfinally thethe problemproblem cancan b

5、ebe summedsummed upup inin networknetwork diagram,diagram, andand allall thethe pathspaths ofof vertexvertex a a toto b,b, thethe edgeedge ofof thethe weightsweights ofof thethe sumsum ofof thethe minimumminimum path.path.keywords:keywords: minimumminimum spanningspanning treetreeprimprim algorithma

6、lgorithm c+c+ languagelanguage sourcesource programprogram互联网 2目 录一、问题描述一、问题描述 .41.1 题目内容题目内容 .41.2 基本要求基本要求 .4二、需求分析二、需求分析 .4三、概要设计三、概要设计 .43.1 邻接矩阵的建立邻接矩阵的建立.53.2 图的建立图的建立 .53.3 求最小生成树求最小生成树.6四、数据结构设计四、数据结构设计.7五、算法设计五、算法设计 .85.1 算法分析算法分析 .85.2 算法实现算法实现 .8六、程序测试与实现六、程序测试与实现 .96.1 主程序主程序.96.2 测试结果测试

7、结果.10七、调试分析七、调试分析.10八、遇到的问题及解决办法八、遇到的问题及解决办法.10九、心得体会九、心得体会.10十、附录十、附录 .11互联网 2一、一、 问题描述问题描述1 题目内容：给定一个地区的 n 个城市间的距离网，用 prim 算法建立最小生成树，并计算得到的最小生成树的代价。2 基本要求：a) 城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。 （要求至少 10 个城市，15 条边）b) 最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。二、二、 需求分析需求分析本程序的功能包括图的建立（采用邻接矩阵存储）和求最

8、小生成树。1图的建立涉及到顶点数组 datan和邻接矩阵 edgenn，顶点数组运用顺序表完成，操作有：顶点的插入即顺序表的插入；邻接矩阵的建立，操作有：插入弧和对应的权值,输出邻接矩阵2最小生成树是通过 prim 算法完成的。prim 里涉及到候选最短边集，用数组 shortedgen表示候选最短边集，数组元素包括候选最短边的的邻接点（adjvex）和权值（lowcost）两个域三、三、 概要设计概要设计互联网 21. 邻接矩阵的建立邻接矩阵的建立1邻接矩阵的初始化，顶点自己对自己的权值为 0，其余的权值均为 maxweight（自定义的无穷大,999）adjmatgraph:adjmatg

9、raph(const int sz)/sz 是顶点数，有参构造函数for(int i=0;isz;i+)for(int j=0;jsz;j+)if(i=j)edgeij=0;elseedgeij=maxweight;/无穷大numofedges=0;2邻接矩阵中点与点之间有弧的，则将两个顶点之间的权值设为 weight 取代 maxweight（无穷大,999）void adjmatgraph:insertedge(const int v1,const int v2,int weight)/插入弧，权为 weightif(v1vertices.listsize()|v2vertices.lis

10、tsize()cout参数 v1,v2 有误 2endl;exit(0);edgev1v2=weight;edgev2v1=weight;numofedges+;2. 图的建立图的建立struct rowcolweight/边信息三元组int row;int col;int weight;互联网 2void adjmatcreategraph(adjmatgraph &g,datatype v,int n,rowcolweight e,int e)/用一个存储边权信息的三元组来生成图int i;for( i=0;in;i+)g.insertvertex(vi);/填充顶点信息for(i=0;i

11、e;i+)g.insertedge(ei.row,ei.col,ei.weight);3. 求最小生成树求最小生成树struct shortedgeint lowcost;int adjvex;void adjmatgraph:prim()int k,w,cost=0;for(int i=1;inumofvertices();i+)shortedgei.lowcost=edge0i;shortedgei.adjvex=0;shortedge0.lowcost=0;for(int i=1;inumofvertices();i+)w=maxweight ;for(int j=1;jnumofver

12、tices();j+)if(shortedgej.lowcost!=0 & shortedgej.lowcostw)w=shortedgej.lowcost;k=j;shortedgek.lowcost=0;for(int j=1;jnumofvertices();j+)if(edgekj shortedgej.lowcost)shortedgej.lowcost=edgekj;shortedgej.adjvex=k;互联网 2cout最小生成树为：endl;for(int i=1;inumofvertices();i+)coutishortedgei.adjvex-edgeishortedg

13、ei.adjvexendl;cost=cost+edgeishortedgei.adjvex;cout最小生成树代价为：costendl;四、 数据结构设计数据结构设计元素类型，结点类型class seqlistprivate:datatype datamaxlistsize;int size;public:seqlist();int listsize()const;/返回元素的个数 sizevoid insert(const datatype & item,int pos);/在位置 pos 插入元素 item;struct rowcolweight/边信息三元组int row;int co

14、l;int weight;struct rowcolweight/边信息三元组int row;int col;int weight;class adjmatgraphprivate:seqlist vertices;/用顺序表存储结点信息int edgemaxverticesmaxvertices;/用数组存储带权或不带权的边互联网 2int numofedges;/边数shortedge shortedgemaxsize;public:adjmatgraph(const int sz=maxvertices);/有参构造函数,sz 为顶点数int numofvertices()/返回结点数目

15、return vertices.listsize();int numofedge()/返回边数return numofedges;void insertvertex(const vert &vertex);/插入结点 vertexvoid insertedge(const int v1,const int v2,int weight);/插入弧，权为 weightvoid printmgraph();void prim();五、五、 算法设计算法设计1. 算法分析算法分析根据用 prim 算法求最小生成树，设 g=(v,e)是具有 n 个顶点的连通网，t=(u,te)是 g 的最小生成树，t

16、的初始状态为 u=u0( u0v）),te= ,重复执行下述操作：在所有 uu,vv-u 的边中找一条代价最小的边（u，v）并入集合 te,同时 v 并入 u,直至 u=v0,最后计算得到的最小生成树的代价2. 算法实现算法实现void adjmatgraph:prim()int k,w,cost=0;for(int i=1;inumofvertices();i+)shortedgei.lowcost=edge0i;shortedgei.adjvex=0;shortedge0.lowcost=0;互联网 2for(int i=1;inumofvertices();i+)w=maxweight

17、;for(int j=1;jnumofvertices();j+)if(shortedgej.lowcost!=0 & shortedgej.lowcostw)w=shortedgej.lowcost;k=j;shortedgek.lowcost=0;for(int j=1;jnumofvertices();j+)if(edgekj shortedgej.lowcost)shortedgej.lowcost=edgekj;shortedgej.adjvex=k;cout最小生成树为：最小生成树为：endl;for(int i=1;inumofvertices();i+)coutishorted

18、gei.adjvex-edgeishortedgei.adjvexendl;cost=cost+edgeishortedgei.adjvex;cout最小生成树代价为：最小生成树代价为：costendl;六、六、 程序测试与实现程序测试与实现1.主程序主程序void main()adjmatgraph g;char a=a,b,c,d,e,f,g,h,i,j;rowcolweight rcw=0,4,1,0,1,2,4,5,3,0,5,4,1,5,5,5,6,6,1,2,7,2,6,8,2,7,9,2,3,10,3,7,11,3,9,12,8,9,13,7,8,14,6,7,15;int n=

19、10,e=15;/10 个顶点，个顶点，15 条边条边adjmatcreategraph(g,a,n,rcw,e);cout 当前的顶点个数为：当前的顶点个数为： g.numofvertices() endl;互联网 2 cout 当前的边的条数为：当前的边的条数为： g.numofedge() endl;g.printmgraph();g.prim();2.测试结果（测试结果（999 是我自己设置的无穷大）是我自己设置的无穷大）七、 调试分析调试分析1图的邻接矩阵是一个 n*n 的矩阵，所以其空间代价是 o(n2)2在求解最小生成树的过程中，会不断的读取任意两个顶点之间边的权值，所以采用邻接

20、矩阵八、 遇到的问题及解决办法遇到的问题及解决办法在求解利用 prim 求解最小生成树的过程中，算法能够看懂，但是利用 c+程序去实现，还是有问题的。最后反复看代码，构造了互联网 2一个最短候选边集，即数组 shortedgen。九、九、 心得体会心得体会本次课程设计用到了顺序表的建立与插入，图的邻接矩阵存储，最本次课程设计用到了顺序表的建立与插入，图的邻接矩阵存储，最终实现了求终实现了求 n 个个城市城市之间的相同公路之间的最短距离，我主要学到之间的相同公路之间的最短距离，我主要学到了将实际问题转换为自己所学到的知识，做到了学以致用。了将实际问题转换为自己所学到的知识，做到了学以致用。十、十

21、、 附录（源代码）附录（源代码）seqlist.h#includeusing namespace std;class seqlistprivate:datatype datamaxlistsize;int size;public:seqlist();int listsize()const;/返回元素的个数返回元素的个数 sizevoid insert(const datatype & item,int pos);/在位置在位置 pos 插入元素插入元素 item;seqlist:seqlist()size=0;int seqlist:listsize()constreturn size;voi

22、d seqlist:insert(const datatype & item,int pos)/在位置在位置 pos 插入元素插入元素 itemint i;if(size=maxlistsize)cout顺序表已满无法插入！顺序表已满无法插入！endl;exit(1);互联网 2if(possize)/当当 pos 等于等于 size 时表示插入在最后时表示插入在最后cout参数参数 pos 越界出错越界出错!pos;i-)datai=datai-1;datapos=item;/在在 pos 位置插入位置插入 itemsize+;/数据元素个数数据元素个数 size 加加 1adjmatgra

23、phlib.hstruct rowcolweight/边信息三元组边信息三元组int row;int col;int weight;void adjmatcreategraph(adjmatgraph &g,datatype v,int n,rowcolweight e,int e)/用一个存储边权信息的三元组来生成图用一个存储边权信息的三元组来生成图int i;for( i=0;in;i+)g.insertvertex(vi);/填充顶点信息填充顶点信息for(i=0;ie;i+)g.insertedge(ei.row,ei.col,ei.weight);adjmatgraph.h#incl

24、udeconst int maxsize=100;struct shortedgeint lowcost;int adjvex;class adjmatgraphprivate:seqlist vertices;/用顺序表存储结点信息用顺序表存储结点信息int edgemaxverticesmaxvertices;/用数组存储带权或不带权的边用数组存储带权或不带权的边互联网 2int numofedges;/边数边数shortedge shortedgemaxsize;public:adjmatgraph(const int sz=maxvertices);/有参构造函数有参构造函数,sz 为

25、顶点数为顶点数int numofvertices()/返回结点数目返回结点数目return vertices.listsize();int numofedge()/返回边数返回边数return numofedges;void insertvertex(const vert &vertex);/插入结点插入结点 vertexvoid insertedge(const int v1,const int v2,int weight);/插入弧插入弧，权为，权为weightvoid printmgraph();void prim();adjmatgraph:adjmatgraph(const int

26、sz)/sz 是顶点数，有参构造函数是顶点数，有参构造函数for(int i=0;isz;i+)for(int j=0;jsz;j+)if(i=j)edgeij=0;elseedgeij=maxweight;/无穷大无穷大numofedges=0;void adjmatgraph:insertvertex(const vert &vertex)/插入结点插入结点 vertexvertices.insert(vertex,vertices.listsize();void adjmatgraph:insertedge(const int v1,const int v2,int weight)/插入

27、弧插入弧，权为权为 weightif(v1vertices.listsize()|v2vertices.listsize()cout参数参数 v1,v2 有误有误 2endl;exit(0);互联网 2edgev1v2=weight;edgev2v1=weight;numofedges+;void adjmatgraph:printmgraph()cout邻接矩阵是：邻接矩阵是：endl;for(int i=0;inumofvertices();i+)for(int j=0;jnumofvertices();j+)coutsetw(10)edgeij;coutendl;coutendl;void adjmatgraph:prim()int k,w,cost=0;for(int i=1;inumofvertices();i+)shortedgei.lowcost=edge0i;shortedgei.adjvex=0;shortedge0.lowcost=0;for(int i=1;inumofvertices();i+)w=maxweight ;for(int j=1;jnumofvertices();j+)if(shortedgej.lowcost!=0 & shortedgej