构造可以使n个城市连接的最小生成树课案

1、数据结构课程设计报告设计题目:构造可以使n个城市连接的最小生成树姓名：学号：专业：物联网工程（嵌入式培养）院系：计算机技术与科学学院班级:1405指导教师：2016年04月09日第 页共17页摘要本次课程设计的要求是给定一个地区的n个城市间的距离网用Prim算法建立最小生成树.并计算得到的最小生成树的代价。将该地区的城市用顶点表示,城市间的公路用边表示.公路的长度作为边的权值.最终这个问题可以归结为网图中求顶点A到顶点B的所有路径中，边的权值之和最少的那条路槿。关键词：最小生成树Prim算法C+语言源程序AbstractThecurriculumdesignrequirementsisgive

2、naregionncity,thedistancebetweenthenetwiththePrimalgorithmtoestablishminimumspanningtree,andcalculatedthepriceofminimumspanningtreeCitiesintheregionwithvertexsaid,betweenhighwayinthecityedge,saidthelengthoftheroadastheedgeoftherightvalues,finallytheproblemcanbesummedupinnetworkdiagram,andallthepaths

3、ofvertexAtoB,theedgeoftheweightsofthesumoftheminimumpathKeywords：minimumspanningtreePrimalgorithmC+languagesourceprogramTOC o 1-5 h z HYPERLINK l bookmark8 o Current Document 一、问题描述4题目内容41.2基本要求4 HYPERLINK l bookmark10 o Current Document 二、需求分析4 HYPERLINK l bookmark12 o Current Document 三、概要设计43.1邻接

4、矩阵的建立3.2图的建立 HYPERLINK l bookmark24 o Current Document 33求最小生成树6 HYPERLINK l bookmark26 o Current Document 四、数据结构设计7 HYPERLINK l bookmark28 o Current Document 五、算法设计85.1算法分析85.2算法实现8 HYPERLINK l bookmark38 o Current Document 六、程序测试与实现96.1主酚96.2测试结果10 HYPERLINK l bookmark40 o Current Document 七、调试分析1

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

6、阵存储）和求最小生成树。图的建立涉及到顶点数组datan和邻接矩阵Edgenn,顶点数组运用顺序表完成，操作有：顶点的插入即顺序表的插入；邻接矩阵的建立，操作有：插入弧和对应的权值，输出邻接矩阵最小生成树是通过Prim算法完成的。Prim里涉及到候选最短边集，用数组shortEdgen表示候选最短边集，数组元素包括候选最短边的的邻接点（adjvex）和权值（lowcost）两个域三、概要设计邻接矩阵的建立邻接矩阵的初始化，顶点自己对自己的权值为0,其余的权值均为MnxWeight(自定义的无穷大,999)AdjMatGraph:AdjMatGraph(constmtsz)/sz是顶点数，有参构

7、造函数fbr(inti=0;isz;i+)fbr(iiitj=0jszJ+)If(l=J)Edgeij=0;elseEdgeij1=MaxWeighty/无穷knumOfEdges=0;邻接矩阵中点与点之间有弧的，则将两个顶点之间的权值设为weight取代MaxWeight(无穷大,999)voidAdjMatGraph:InsenEdge(constintvl,constmtv2.iiitweight)插入弧vl,v2A,权为weightif(vlVertices.ListSize()|v2Veitices.ListSize()coutH参数vl,v2有误2Hendl;exit(O);Edg

8、evlv2=weight;Edgev2vl=weight;numOfEdges+;图的建立stmctRowColWeight/边信息三元组iiitrow;iiitcol;iiitweight;voidAdjMatCreateGraph(AdjMatGraph&G；DataTvpeV.iiitn.RowColWeightE,iiite)用一个存储边权信息的三元组来生成图mti;fbr(i=O:in;i+)G.InsertVertex(Vi);/填充顶点信息fbr(i=O;ie;i-H-)G.IiiseitEdge(Ei.iow,Ei.cotEi.weight);求最小生成树stmctshonEd

9、gemtlowcost;iiitadjvex;voidAdjMatGraph:Priin()iiitk,w.cost=0;fbr(inti=l;inumOfVenicesQ;i-H-)shortEdgei.lowcost=Edge0i;shortEdgeiadjvex=0;shonEdge0.lowcost=0;fbr(inti=l;inumOfVeiticesQ;i-H-)w=MaxWeight;fbr(mtj=ljnumOfVeiticesQ;j+)if(shoitEdgej.lowcost!=0&shortEdgej.Iowcostw)w=shortEdgejlowcost;k=J；sh

10、ortEdgek.lowcost=0;fbr(mtj=ljnumOfVeiticesQ;j+)if(EdgekjshonEdgeJj.lowcost)shortEdgej.lowcost=Edgekj;shortEdgej.adjvex=k;coutH最小生成树为：yeiidl;fbr(inti=l;inumOfVenicesQ;i-H-)coutiH-HshonEdgei.adjvexHEdgeishortEdgei.adjvexendl;cost=cost+EdgeishoitEdgei.adjvex;coutM最小生成树代价为:Hcostendl;四、数据结构设计元素类型，结点类型cla

11、ssSeqListprivate:DataTvpedataMaxListSize;mtsize;public:SeqListQ;intListSizeQconst;/返回元素的个数sizevoidIiisert(constDataTe&itemiiitpos);在位置pos插入元素item;stiuctRowColWeight/边信息三元组imtrow;mtcol;mtweight;stmctRowColWeight/边信息三元组imtrow;mtcol;mtweight;classAdjMatGraphiprivate:SeqListVenices;/用顺序表存储结点信息mtEdgeMaxV

12、erticesMaxVertices;/用数组存储带权或不带权的边mtnumOfEdges;/边数shonEdgeshortEdgeMaxSize;public:AdjMatGraph(constintsz=MaxVertices);有参构造函数,sz为顶点数iiitnumOfVertices()/返回结点数目returnVeitices.ListSize();mtnumOfEdge()返回边数returnnumOfEdges;voidIiisenVenex(constVeiT&vert亡x);插入结点vertexvoidIiisertEdge(constintvl,constintv2,in

13、tweight);/插入弧权为weightvoidpimtMGraph();voidPrim();五、算法设计算法分析根据用Pnm算法求最小生成树，设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树,T的初始状态为U=uo(uoFV),TE=,重复执行下述操作:在所有uU,vFV-U的边中找一条代价最小的边(11,v)并入集合TE,同时v并入U,直至U=V0,最后计算得到的最小生成树的代价算法实现voidAdjMatGraph:Prim()intk,w,cost=0;for(inti=1;inumOfVertices();i+)shortEdgeilowcost=Edge

14、0l;shortEdgei.adjvex=0;shortE(lge0.Iowcost=0;for(inti=l;inumOfyrertices();i+)w=MaxWeight;for(intj=lnumOfVertices()+)if(shortEdgeJowcost!=0&shortEdgejJowcostw)w=shortEdgej.Iowcost;k=j；shortEdgek.Iowcost=0;for(intj=lijnumOfVertices()+)if(EdgekjshortEdgejJowcost)shortEdgejJowcost=Edgekj;shortEdgej.adjv

15、ex=k;coutn最小生成树为：vvendl;for(inti=1;inumOfVerticesO；i+)coutvvivv”vvshortEdgei.adjvexvv”EdgeishortEdgei.adjvexend1；cost=cost+EdgeishortEdgei.adjvex;coutu最小生成树代价为:*costendl;六、程序测试与实现1.主程序voidmain()AdjMatGraphg;chara=,A,BVC,DyE,F,G,HVI,J,;RowColWeightrcw=0,4,l,0,U,4,53,0,5,4,l,5,5,6,6,U,7,2,6,8,2,7,9,2,

16、3,10,3,7,11,3,9,12,8,9,13,7,8,14,6,7,15;intn=10,e=15/10个顶点，15条边AdjMatCreateGraph(g,a,n,rcw,e);cout当前的顶点个数为：Hg.numOfVertices()endl;cout”当前的边的条数为：”vvg.numOfEdgeOendl;g.printMGraph();g.PrimO;2.测试结果（999是我自己设置的无穷大）S3C:windowssystem32cmd.exe一口L当前的顶点亍歛対当前的边的条数为邻接拒阵是，0:10=15299999914999999999999207999999599

17、99999999999990109999998999999999999910099999999911999121699999999039999999999994599999930699999999999999989999996015999999999999911999999150149999995999999999999999991401399999999912999999999999130最小生成02TOC o 1-5 h z172100143562g913312杲小生駆代价为，63请按任意継继级中文简休)-手心输人注七、调试分析图的邻接矩阵是一个n*n的矩阵，所以其空间代价是O(i?)在求

18、解最小生成树的过程中，会不断的读取任意两个顶点之间边的权值，所以采用邻接矩阵八、遇到的问题及解决办法在求解利用Pmn求解最小生成树的过程中，算法能够看懂，但是利用C+程序去实现，还是有问题的。最后反复看代码，构造了一个最短候选边集，即数组shoitEdgen九、心得体会本次课程设计用到了顺序表的建立与插入，图的邻接矩阵存储，最终实现了求n个城市之间的相同公路之间的最短距离，我主要学到了将实际问题转换为自己所学到的知识，做到了学以致用。十、附录（源代码）SeqList.h#includeusingnamespacestd;classSeqListprivate:DataTypedataMaxLi

19、stSize;intsize;public:SeqList();intListSize()const;/j&回元素的个数sizevoidInsert(constDataType&itemjntpos);在位置pos插入元素item;SeqList:SeqList()size=O;intSeqList:ListSize()constreturnsize;voidSeqList:Insert(constDataType&itemjntpos)/在位置pos插入元素iteminti;if(size=MaxListSize)coutu顺序表已满无法插入！vvendl;exit(l);_if(possi

20、ze)/当pos等于size时表示插入在最后coutft参数pos越界出错!,fendl;exit(l);从后向前把前一个元素迁移到后一个元素位置直到存储位置pos为止for(i=size;ipos;i)datai=datai-l;datnpos=item;在pos位置插入itemsize*”/数据元素个数size加1AdjMatGraphLib.hstructRowColWeight/边信息三元组introw；intcol；intweight；;voidAdjMatCreateGraph(AdjMatGrapli&GQmtiiTypeV,intn,RowColWeightE,int可/用_个

21、存储边权信息的三元组来生成图inti;for(i=O;in;i+)G.InsertVertex(Vi)；/填充顶点信息for(i=0；i,权为weightvoidprintMGraph();voidPrimO；;AdjMatGraph:AdjMatGraph(constintsz)/sz是顶点数p有参构造函数for(inti=O;i.权为weightif(vlVertices.ListSize()|v2Vertices.ListSize()coutf,参数vl,y2有误2nendl;exit(O);Edgevlv2=weight;Edgev2vl=weight;numOfEdges+;void

22、AdjMatGraph:printMGraph()coutn邻接矩阵是:r,endl；for(inti=0；inumOfVertices()；i+)for(intj=0;jnumOfVerticesO；j+)coutsetw(10)Edgeij;coutendl;coutendl;voidAdjMatGraph:Prim0intk,w,cost=0;for(inti=l；inumOfVerticesO；i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0；shortEdge0.lowcost=0;for(inti=l；inumOfVerticesO；i+)w=MaxWeight;for(intj=l；jnumOfVerticesO；j+)if(shortEdgej.lowcost!=0&shortEdgej.lowcostw)w=shortEdgej.lowcost;k=j；shortEdgek.lowcost=0;for(intj=l；jnumOfVerticesO；j+)if(EdgekjshortEdgej.lowcost)shortEdgej.l