最小生成树问题

《最小生成树问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Projectl设计报告选题名称:最小生成树问题学院:计算机工程学院专业:计算机科学与技术NIIT班级：计算机1147姓名：刘建成学号：1141317722指导教师:李笑平张亚红殷路学年学期：2015〜2016学年第1学期1课题需求描述错误！未定义书签。2总体功能与数据结构设计错误！未定义书签。2.1总体功能结构错误！未定义书签。2.2数据结构设计4调试与测试算法设计和程序设计错误！未定义书签。5Project设计总结错误！未定义书签。参考文献1:课题需求描述1.1课题题目：最小生成树问题：若要在n个城市之间建设通信网络，只需要假设ml条线路即可。如何以最低的经

2、济代价建设这个通信网，是一个网的最小生成树问题。1.2需求描述：（1）利用克鲁斯卡尔算法求网的最小生成树。（2）实现教材6.5节屮定义的抽象数据类型MFSeto以此表示构造生成树过程中的连通分量。（3）以文木的形式输出生成树中各条边以及他们的权值。（ac3）5、选做内容：利用堆排序（参见教科书1043节）实现选择权值最小的边数据结构设计程序主要利用图的结构生成图，再利用克鲁斯卡尔算法求出最小生成树。3：算法设计和程序设计3.1设计原理（1）通信线路一旦建立，必然是双向的。因此，构造生成树的网一定是无向的，设图的顶点个数不超过30个，并为就简单起见，网屮边的权值设

3、成小于100的整数，可利用c语言提供的随机函数产生。图的存储结构的选取应和所做操作相适应。（2）为了便于选择权值最小边，此题的存储结构不应选择邻接矩阵的数组表示法，也不选取邻接表，而是以存储边（带权）的数组表示图。3.2概要设计1）抽象数据类型（ADT）如下：ADTGRAPH{数据对彖V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={lv,w屈于V且P（v,w）,表示从v到w的弧，谓词P（v,w）定义了弧vv,w>的意义或信息}基木操作P:CreateGmph(&G,V,VR)初始条件：v是图的顶点集，VR是图

4、屮弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G)初始条件：图G存在。操作结果：销毁图GLocateVex(G,u)初始条件：图G存在，u和G屮定点有相同特征。操作结果：若图G中存在顶点U,则返回顶点在图中的位置：否则返回其他信息。GetVex(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返冋v的值tPutVex(&G,v,value)...初始条件：图G存在。操作结果：对v賦值valueo2)存储结构typedefstmct{intbegin;intend;intweight;}edge;typedefstmct{in

5、tadj:intweight;}AdjMatrix[MAX][MAX];typedefstmct{AdjMatrixarc;intvexnum,arcnum;}MGraph:流程图:输入给定图的边数和顶点数该函数中主要有6段代码，分别是图的构建代码，对权值排序的代码，交换权值代码，最小生成数代码，找尾代码，主函数代码。6段代码分别实现不同的功能,共同满足题目所需要求。4：调试与测验4.1：调试分析终于，在老师的耐心指导和同学的帮助匚我的课设任务完成了。通过这次课程设计屮遇到的许多问题，我收获颇多，下而就谈一谈我遇到的一个主要问题及相应的产生原因。问题：顶点名的类

6、型识别.现象当用字母表示顶点时，程序进入死循环。原現顶点名称与顶点数M于同一数据类型即足int整形，当出现类型冲突时，程序不能识别就会发生冲突。4.2：测验1）事例524536656-

7、O

8、x

9、请输入2与3N间的权值:5请输入有边的2个顶点25请输入2与5之间的权值:3请输入有边的2个顶点53请输入5与3之间的权值I右持］—&屯丁」2、［工点56请输入5与6之间的权值:6情输入有边的2个顶点36请输入3与6之间的权值：4请输入有边的2个顶点34请输入3与4之间的权值：4请输入有边的2个顶点465>project设计总结通过这次试验更深刻的理解了什么是图，怎么样去

10、创造图，利用图來解决实际问题,利用克鲁斯卡尔算法去解决最小生成树问题。参考文献《数据结构（Ci吾言版）》严蔚敏吴伟民编著淸华人学出版社《数据结构严蔚皱》（教学视频）《数据结构锌法实现及解析》髙一凡四安电子科技大学岀版社