数据结构课程设计求最小生成树.doc

《数据结构课程设计求最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、##大学数据结构课程设计报告题目：图的最小生成树院（系）：学生姓名:班级：学号:起迄日期:指导教师:指导教师评语：成绩：签名：年月日2011—2012年度第2学期一、需求分析1.问题描述：设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。该题目需要运用最小生成树来解决。最小生成树的代价之和最小，所以是一种最经济的架设方法。2.基本功能该程序是解决城市间架设网络问题的，采用邻接表与邻接矩阵对构造的图进行存储，用普利姆与克鲁斯卡尔算法进行求解。3.输入输

2、出首先输入顶点的个数以及边的个数，格式如:46。然后输入边的权值，格式如：ab1。输出分为四种输出，输出邻接表，邻接矩阵，普利姆算法求得的最小生成树，克鲁斯卡尔求得的最小生成树。最小生成树的格式为：<顶点名顶点名>权值。二、概要设计1.设计思路：问题的解决分别采用普利姆算法已经克鲁斯卡尔算法。1）普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，依此类推，如果到达最后一个则返回上一个顶点。2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的

3、边，然后写出第二小的，依此类推，最终要有个判断是是否生成环，不生成则得到克鲁斯卡尔的最小生成树。2.数据结构设计：1.抽象数据类型如下：ADTGraph{数据对象V：v是具有相同特征的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={

4、v,w属于v且p（v,w）表示从v到w的弧，谓词p（v,w）定义了弧的意义或信息}基本操作：1)GreatGraph（&G,V,VR）；初始条件：V是图的顶点集，VR是图中弧的集合。操作条件：按V和VR的定义构造图G。2）LocateVex（

5、G,u）；初始条件：图G存在，u和G中顶点有相同的特征。操作条件：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。2.存储结构typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];//定义一个顶点数组AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;typedefstructarcnode//弧结点{intadjvex;//该弧指

6、向的顶点的位置structarcnode*nextarc;//弧尾相同的下一条弧char*info;//该弧信息}arcnode;typedefstructvnode//邻接链表顶点头接点{chardata;//结点信息arcnode*firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;3.软件结构设计：开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3.PRIM算法4.kruscal算法结束三、详细设计1．主函数和其他函数的伪码算法主函数：voidmain(){alg

7、raphgra;MGraph_LG;inti,j,d,g[20][20];chara='a';d=creatMGraph_L(G);creatadj(gra,G);cout<<"**********************************"<

8、<"**4。KRUSCAL算法最经济的架设方法**"<>s;switch(s){case1:cout<<"用邻接矩阵存储为："<

9、se3:for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j)g[i+1][j+1]=G.arcs[i][j].adj;cout<<"PRIM算法最经济的架设方法为:"<