最小生成树课程设计

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

1、江西理工大学应用科学学院数据结构课程设计课程名称:数据结构题目:最小生成树问题年级/专业/班:08级计算机科学与技术一班学生姓名:许林红学号:08060508124指导教师:康岚兰开题时间:2010年6月21日完成时间:2010年7月2日14江西理工大学应用科学学院数据结构课程设计课程名称:数据结构题目:最小生成树问题年级/专业/班:08级计算机科学与技术一班学生姓名:许林红学号:08060508124指导教师:康岚兰开题时间:2010年6月21日完成时间:2010年7月2日14目录摘要2一、引言3二、设计目的与任务31、课程设计目的32、课程设计的任务3三、设计

2、方案41、需求分析42、概要设计43、详细设计5四、调试分析与体会9五、运行结果10六、结论12七、感想12八、参考文献1214摘要最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法求最小生成树。Kruskal算法和Prim算法是求最小生成树的常用算法它们分别适用于稠密图和稀疏图。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆,构建造价最低的通讯网络。关键词：最小生成

3、树；Kruskal算法；Prim算法AbstractTheminimumCostspanningtreedatastructureisanimportantapplicationofChinese,inthepicturefornvertexevenTongWangcancreatemanydifferentspanningtree,minimumspanningtreeisinallspanningtreeinthetotalcostoftheminimumspanningtree.Thiscourseisdesignedasafigureoftheadjacenc

4、ymatrixstoragestructure,weadoptPrimandKruskalminimumspanningtreealgorithm.KruskalPrimalgorithmandminimumspanningtreealgorithmisusedforthealgorithmrespectivelyapplicableandsparselypopulated.Minimumspanningtreeisverywideapplicationinmines,suchastheventilationdesignandmodificationandoptimi

5、zationinhowtosetuptheshortestcablenetwork,constructingthelowestcostofcommunicationsnetworkKeywords:MinimumCostSpanningTree；Kruskalalgorithm；Primalgorithm14《数据结构》课程设计------最小生成树一、引言《数据结构》是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并

6、对性能进行分析和比较，内容非常丰富。本课程设计我们要解决的问题是图最小生成树问题。要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。本课程设计要解决的问题构造连通网的最小生成树,我们首先要做的是创建一个邻接矩阵，用以来存储图，然后我们要想好怎样利用普里姆算法和克鲁斯卡尔算法来构造最小生成树。把这两种算法写入主函数，调试好程序。最后写好报告。二、设计目的与任务1、课程设计目的本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码

7、、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。2、课程设计的任务问题描述:已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。14三、设计方案1、需求分析1)建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表明节点间的连通