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

《数据结构》课程设计报告设计题目：构造可以使n个城市连接的最小生成树姓名：学号：专业：物联网工程（嵌入式培养）院系：计算机技术与科学学院班级：1405指导教师：2016年01月09日第1页共16页摘要本次课程设计的要求是给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。将该地区的城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，最终这个问题可以归结为网图中，求顶点A到顶点B的所有路径中，边的权值之和最少的那条路径。关键词：最小生成树Prim算法C++语言源程序第2页共16页AbstractThecurriculumdesignrequirementsisgivenaregionncity,thedistancebetweenthenetwiththePrimalgorithmtoestablishminimumspanningtree,andcalculatedthepriceofminimumspanningtree.Citiesintheregionwithvertexsaid,betweenhighwayinthecityedge,saidthelengthoftheroadastheedgeoftherightvalues,finallytheproblemcanbesummedupinnetworkdiagram,andallthepathsofvertexAtoB,theedgeoftheweightsofthesumoftheminimumpath.Keywords:minimumspanningtreePrimalgorithmC++languagesourceprogram第3页共16页目录一、问题描述.........................................................................................................................41.1题目内容.................................................................................................................................41.2基本要求.................................................................................................................................4二、需求分析.........................................................................................................................4三、概要设计.........................................................................................................................43.1邻接矩阵的建立......................................................................................................................53.2图的建立.................................................................................................................................53.3求最小生成树..........................................................................................................................6四、数据结构设计................................................................................................................7五、算法设计.........................................................................................................................85.1算法分析.................................................................................................................................85.2算法实现.................................................................................................................................8六、程序测试与实现............................................................................................................96.1主程序.....................................................................................................................................96.2测试结果...............................................................................................................................10七、调试分析.......................................................................................................................10八、遇到的问题及解决办法.............................................................................................10九、心得体会.......................................................................................................................10十、附录...............................................................................................................................11第4页共16页一、问题描述1．题目内容：给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。2．基本要求：a)城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。（要求至少10个城市，15条边）b)最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。二、需求分析本程序的功能包括图的建立（采用邻接矩阵存储）和求最小生成树。①图的建立涉及到顶点数组data[n]和邻接矩阵Edge[n][n]，顶点数组运用顺序表完成，操作有：顶点的插入即顺序表的插入；邻接矩阵的建立，操作有：插入弧和对应的权值,输出邻接矩阵②最小生成树是通过Prim算法完成的。Prim里涉及到候选最短边集，用数组shortEdge[n]表示候选最短边集，数组元素包括候选最短边的的邻接点（adjvex）和权值（lowcost）两个域三、概要设计1.邻接矩阵的建立第5页共16页①邻接矩阵的初始化，顶点自己对自己的权值为0，其余的权值均为MaxWeight（自定义的无穷大,999）AdjMatGraph::AdjMatGraph(constintsz)//sz是顶点数，有参构造函数{for(inti=0;isz;i++)for(intj=0;jsz;j++){if(i==j)Edge[i][j]=0;elseEdge[i][j]=MaxWeight;//无穷大}numOfEdges=0;}②邻接矩阵中点与点之间有弧的，则将两个顶点之间的权值设为weight取代MaxWeight（无穷大,999）voidAdjMatGraph::InsertEdge(constintv1,constintv2,intweight)//插入弧v1,v2，权为weight{if(v10||v1Vertices.ListSize()||v20||v2Vertices.ListSize()){cout参数v1,v2有误2endl;exit(0);}Edge[v1][v2]=weight;Edge[v2][v1]=weight;numOfEdges++;}2.图的建立structRowColWeight//边信息三元组{introw;intcol;intweight;};voidAdjMatCreateGraph(AdjMatGraph&G,DataTypeV[],intn,RowColWeightE[],inte)//用一个存储边权信息的三元组来生成图{inti;第6页共16页for(i=0;in;i++)G.InsertVertex(V[i]);//填充顶点信息for(i=0;ie;i++)G.InsertEdge(E[i].row,E[i].col,E[i].weight);}3.求最小生成树structshortEdge{intlowcost;intadjvex;};voidAdjMatGraph::Prim(){intk,w,cost=0;for(inti=1;ithis-numOfVertices();i++){shortEdge[i].lowcost=Edge[0][i];shortEdge[i].adjvex=0;}shortEdge[0].lowcost=0;for(inti=1;ithis-numOfVertices();i++){w=MaxWeight;for(intj=1;jthis-numOfVertices();j++){if(shortEdge[j].lowcost!=0&&shortEdge[j].lowcostw){w=shortEdge[j].lowcost;k=j;}}shortEdge[k].lowcost=0;for(intj=1;jthis-numOfVertices();j++){if(Edge[k][j]shortEdge[j].lowcost){shortEdge[j].lowcost=Edge[k][j];shortEdge[j].adjvex=k;}}}cout最小生成树为：endl;for(inti=1;ithis-numOfVertices();i++)第7页共16页{cou