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

《构造可以使n个城市连接的最小生成树[互联网+].doc》由会员分享，可在线阅读，更多相关《构造可以使n个城市连接的最小生成树[互联网+].doc（18页珍藏版）》请在三一文库上搜索。

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

2、建立最小生成树，并计算得到的最小生成 树的代价。将该地区的城市用顶点表示，城市间的公路用树的代价。将该地区的城市用顶点表示，城市间的公路用 边表示，公路的长度作为边的权值，最终这个问题可以归边表示，公路的长度作为边的权值，最终这个问题可以归 结为网图中，求顶点结为网图中，求顶点 A A 到顶点到顶点 B B 的所有路径中，边的权值的所有路径中，边的权值 之和最少的那条路径。之和最少的那条路径。 关键词：关键词： 最小生成树最小生成树 PrimPrim 算法算法 C+C+语言源程序语言源程序 互联网 2 Abstract TheThe currcurriculumiculum designdes

3、ign requirementsrequirements is is 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 minimum

4、minimum spanningspanning tree.tree. CitiesCities in in thethe regionregion withwith vertexvertex said,said, betweenbetween highwayhighway in in thethe citycity edge,edge, saidsaid thethe lengthlength ofof thethe roadroad asas thethe edgeedge ofof thethe rightright values,values, finallyfinally theth

5、e problemproblem cancan bebe summedsummed upup in in 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

6、treetree PrimPrim algorithmalgorithm C+C+ languagelanguage sourcesource programprogram 互联网 2 目 录 一、问题描述一、问题描述 .4 1.1 题目内容题目内容 .4 1.2 基本要求基本要求 .4 二、需求分析二、需求分析 .4 三、概要设计三、概要设计 .4 3.1 邻接矩阵的建立邻接矩阵的建立.5 3.2 图的建立图的建立 .5 3.3 求最小生成树求最小生成树.6 四、数据结构设计四、数据结构设计.7 五、算法设计五、算法设计 .8 5.1 算法分析算法分析 .8 5.2 算法实现算法实现 .8

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

8、及其权值，并显示得到的最小生成 树的代价。 二、二、 需求分析需求分析 本程序的功能包括图的建立（采用邻接矩阵存储）和求最小生成树。 1图的建立涉及到顶点数组 datan和邻接矩阵 Edgenn，顶点 数组运用顺序表完成，操作有：顶点的插入即顺序表的插入；邻接 矩阵的建立，操作有：插入弧和对应的权值,输出邻接矩阵 2最小生成树是通过 Prim 算法完成的。Prim 里涉及到候选最 短边集，用数组 shortEdgen表示候选最短边集，数组元素包括候选 最短边的的邻接点（adjvex）和权值（lowcost）两个域 三、三、 概要设计概要设计 互联网 2 1. 邻接矩阵的建立邻接矩阵的建立 1邻

9、接矩阵的初始化，顶点自己对自己的权值为 0，其余的 权值均为 MaxWeight（自定义的无穷大,999） AdjMatGraph:AdjMatGraph(const int sz)/sz 是顶点数，有参构造函数 for(int i=0;isz;i+) for(int j=0;jsz;j+) if(i=j) Edgeij=0; else Edgeij=MaxWeight;/无穷大 numOfEdges=0; 2邻接矩阵中点与点之间有弧的，则将两个顶点之间的权值 设为 weight 取代 MaxWeight（无穷大,999） void AdjMatGraph:InsertEdge(const i

10、nt v1,const int v2,int weight)/插入弧， 权为 weight if(v1Vertices.ListSize()|v2Vertices.ListSize() cout参数 v1,v2 有误 2endl; exit(0); Edgev1v2=weight; Edgev2v1=weight; numOfEdges+; 2. 图的建立图的建立 struct RowColWeight/边信息三元组 int row; int col; int weight; ; 互联网 2 void AdjMatCreateGraph(AdjMatGraph for( i=0;in;i+)

11、G.InsertVertex(Vi);/填充顶点信息 for(i=0;ie;i+) G.InsertEdge(Ei.row,Ei.col,Ei.weight); 3. 求最小生成树求最小生成树 struct shortEdge int 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;inum

12、OfVertices();i+) w=MaxWeight ; for(int j=1;jnumOfVertices();j+) if(shortEdgej.lowcost!=0 k=j; shortEdgek.lowcost=0; for(int j=1;jnumOfVertices();j+) if(Edgekj shortEdgej.lowcost) shortEdgej.lowcost=Edgekj; shortEdgej.adjvex=k; 互联网 2 cout最小生成树为：endl; for(int i=1;inumOfVertices();i+) coutishortEdgei.a

13、djvex- EdgeishortEdgei.adjvexendl; cost=cost+EdgeishortEdgei.adjvex; cout最小生成树代价为：costendl; 四、 数据结构设计数据结构设计 元素类型，结点类型 class SeqList private: DataType dataMaxListSize; int size; public: SeqList(); int ListSize()const;/返回元素的个数 size void Insert(const DataType /在位置 pos 插入元素 item ; struct RowColWeight/边信

14、息三元组 int row; int col; int weight; ; struct RowColWeight/边信息三元组 int row; int col; int weight; ; class AdjMatGraph private: SeqList Vertices;/用顺序表存储结点信息 int EdgeMaxVerticesMaxVertices;/用数组存储带权或不带权的边 互联网 2 int numOfEdges;/边数 shortEdge shortEdgeMaxSize; public: AdjMatGraph(const int sz=MaxVertices);/有参

15、构造函数,sz 为顶点数 int numOfVertices()/返回结点数目 return Vertices.ListSize(); int numOfEdge()/返回边数 return numOfEdges; void InsertVertex(const VerT /插入结点 vertex void InsertEdge(const int v1,const int v2,int weight);/插入弧，权为 weight void printMGraph(); void Prim(); ; 五、五、 算法设计算法设计 1. 算法分析算法分析 根据用 Prim 算法求最小生成树，设

16、G=(V,E)是具有 n 个顶点的连通 网，T=(U,TE)是 G 的最小生成树，T 的初始状态为 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.lowcos

17、t=0; 互联网 2 for(int i=1;inumOfVertices();i+) w=MaxWeight ; for(int j=1;jnumOfVertices();j+) if(shortEdgej.lowcost!=0 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;inumOfVert

18、ices();i+) coutishortEdgei.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

19、,9,12,8,9,13,7,8,14,6,7,15; int n=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(

20、n2) 2在求解最小生成树的过程中，会不断的读取任意两个顶点之 间边的权值，所以采用邻接矩阵 八、 遇到的问题及解决办法遇到的问题及解决办法 在求解利用 Prim 求解最小生成树的过程中，算法能够看懂，但 是利用 C+程序去实现，还是有问题的。最后反复看代码，构造了 互联网 2 一个最短候选边集，即数组 shortEdgen。 九、九、 心得体会心得体会 本次课程设计用到了顺序表的建立与插入，图的邻接矩阵存储，最本次课程设计用到了顺序表的建立与插入，图的邻接矩阵存储，最 终实现了求终实现了求 n 个个城市城市之间的相同公路之间的最短距离，我主要学到之间的相同公路之间的最短距离，我主要学到 了将

21、实际问题转换为自己所学到的知识，做到了学以致用。了将实际问题转换为自己所学到的知识，做到了学以致用。 十、十、 附录（源代码）附录（源代码） SeqList.h #include using namespace std; class SeqList private: DataType dataMaxListSize; int size; public: SeqList(); int ListSize()const;/返回元素的个数返回元素的个数 size void Insert(const DataType /在位置在位置 pos 插入元素插入元素 item ; SeqList:SeqList

22、() size=0; int SeqList:ListSize()const return size; void SeqList:Insert(const DataType if(size=MaxListSize) cout顺序表已满无法插入！顺序表已满无法插入！endl; exit(1); 互联网 2 if(possize)/当当 pos 等于等于 size 时表示插入在最后时表示插入在最后 cout参数参数 pos 越界出错越界出错!pos;i-) datai=datai-1; datapos=item;/在在 pos 位置插入位置插入 item size+;/数据元素个数数据元素个数 s

23、ize 加加 1 AdjMatGraphLib.h struct RowColWeight/边信息三元组边信息三元组 int row; int col; int weight; ; void AdjMatCreateGraph(AdjMatGraph for( i=0;in;i+) G.InsertVertex(Vi);/填充顶点信息填充顶点信息 for(i=0;ie;i+) G.InsertEdge(Ei.row,Ei.col,Ei.weight); AdjMatGraph.h #include const int MaxSize=100; struct shortEdge int lowc

24、ost; int adjvex; ; class AdjMatGraph private: SeqList Vertices;/用顺序表存储结点信息用顺序表存储结点信息 int EdgeMaxVerticesMaxVertices;/用数组存储带权或不带权的边用数组存储带权或不带权的边 互联网 2 int numOfEdges;/边数边数 shortEdge shortEdgeMaxSize; public: AdjMatGraph(const int sz=MaxVertices);/有参构造函数有参构造函数,sz 为顶点数为顶点数 int numOfVertices()/返回结点数目返回结

25、点数目 return Vertices.ListSize(); int numOfEdge()/返回边数返回边数 return numOfEdges; void InsertVertex(const VerT /插入结点插入结点 vertex void InsertEdge(const int v1,const int v2,int weight);/插入弧插入弧，权为，权为 weight void printMGraph(); void Prim(); ; AdjMatGraph:AdjMatGraph(const int sz)/sz 是顶点数，有参构造函数是顶点数，有参构造函数 for(

26、int i=0;isz;i+) for(int j=0;jsz;j+) if(i=j) Edgeij=0; else Edgeij=MaxWeight;/无穷大无穷大 numOfEdges=0; void AdjMatGraph:InsertVertex(const VerT void AdjMatGraph:InsertEdge(const int v1,const int v2,int weight)/插入弧插入弧， 权为权为 weight if(v1Vertices.ListSize()|v2Vertices.ListSize() cout参数参数 v1,v2 有误有误 2endl; e

27、xit(0); 互联网 2 Edgev1v2=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+) shortEd

28、gei.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 k=j; shortEdgek.lowcost=0; for(int j=1;jnumOfVertices();j+) if(Edgekj shortEdgej.lowcost) shortEdgej.lowcost=Edgekj; 互联网 2 shortEdge

29、j.adjvex=k; cout最小生成树为：最小生成树为：endl; for(int i=1;inumOfVertices();i+) coutishortEdgei.adjvex- EdgeishortEdgei.adjvexendl; cost=cost+EdgeishortEdgei.adjvex; cout最小生成树代价为：最小生成树代价为：costendl; Main.cpp #include typedef char DataType; const int MaxListSize=100; const int SeqQMaxSize=100; #includeSeqList.h

30、const int MaxVertices=100; const int MaxWeight=999; typedef char VerT; #includeAdjMatGraph.h #includeAdjMatGraphLib.h using namespace std; 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=10,e=15;/10 个顶点，个顶点，15 条边条边 AdjMatCreateGraph(g,a,n,rcw,e); cout 当前的顶点个数为：当前的顶点个数为： g.numOfVertices() endl; cout 当前的边的条数为：当前的边的条数为： g.numOfEdge() endl; g.printMGraph(); g.Prim(); 互联网 2