Kruskal算法求最小生成树.doc

《Kruskal算法求最小生成树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、荆楚理工学院课程设计成果学院:_______计算机工程学院__________班级:14计算机科学与技术一班学生姓名:陈志杰学号:2014407020137设计地点（单位）_____B5101_____________________设计题目:克鲁斯卡尔算法求最小生成树__________________________________完成日期：2015年1月6日指导教师评语:___________________________________________________________________________________________________

2、________________________________________________________________________________________________________________________________________________________成绩(五级记分制):________________教师签名:_________________________《数据结构》课程设计评分表班级 计科一班姓名陈志杰 指导教师李素若 题目：克鲁斯卡尔算法求最小生成树评分标准评分标准分数权重评分的依据得分AC选题10选题符合大纲

3、要求，题目较新颖，工作量大选题基本符合大纲要求，工作量适中 工作态度10态度端正，能主动认真完成各个环节的工作，不迟到早退，出勤好。能够完成各环节基本工作，出勤较好。 系统设计20能正确描述总体系统框架图，主要函数有正确的流程图。能基本正确描述总体系统框架图，主要函数基本能给出流程图。 独立解决问题的能力10具有独立分析、解决问题能力，有一定的创造性，能够独立完成数据库及相关软件的设计与调试工作，程序结构合理，逻辑严谨，功能完善。有一定的分析、解决问题能力。能够在老师指导下完成软件的设计与调试工作，程序功能较完善。 答辨问题回答20能准确回答老师提出的问题能基本准确回答老

4、师提出的问题 程序运行情况10程序运行正确、界面清晰，测试数据设计合理。程序运行正确、界面较清晰，能给出合适的测试数据。 课程设计论文20格式规范，层次清晰，设计思想明确，解决问题方法合理，体会深刻。格式较规范，设计思想基本明确，解决问题方法较合理。 总分 指导教师（签字）：注：介于A和C之间为B级，低于C为D级和E级。按各项指标打分后，总分在90～100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。目录1需求分析11.1系统目标11.2主体功能11.3开发环境12概要设计12.1功能模块划分12.2系统流程图23详细设计33.1数据结构33

5、.2模块设计34测试34.1测试数据34.2测试分析45总结与体会65.1总结：65.2体会：6参考文献7附录全部代码81需求分析1.1系统目标Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。其基本思想是：首先选取全部的n个顶点，将其看成n个连通分量；然后按照网中边的权值由小到大的顺序，不断的选取当前未被选取的边集中权值最小的边。依照生成树的概念，n个结点的生成树有n-1条边，故反复上述过程，直到选取了n-1条边为止，就构成了一棵最小生成树。1.2主体功能在城市规划设计中，假设有n个城市之间建立通信网，则连通n个城市只需n-1条线路。这里自然考虑怎

6、样建立这n-1条路是总费用最省。把这n个城市抽象成一个连通网，网的顶点表示各个城市，顶点与顶点之间的边表示通信线路，各个城市之间的通讯线路看作边，相应的建设花费作为边的权，这样就构成了一个网络。由于在n个城市之间，可行线路有(n*(n-1))/2条，那么，如果选择其中的n-1条线路(边)在n个城市间建成全都能相互通讯的网，并且总的建设花费为最小？这就是求该网络的最小生成树问题。本程序的目的是要建立一棵生成树使总费用最少。 1.3开发环境装有Windows7操作系统的PC机vc++6.0，奔腾41.0GHz以上的处理器，编写的程序需要在32MB的内存中运行。推荐在以下基本配

7、置电脑中运行：CPUIntelMMX233MHz内存：64MB硬盘空间：1.5GB显卡：4MB显存以上的PCI、AGP显卡声卡：最新的PCI声卡CD-ROM：8x以上CD-ROM2概要设计2.1功能模块划分运行程序后，程序在内存中申请图g的邻接矩阵表示空间，存放作为用整型数组表示的顶点、边、权值的数据。程序运行过程中调用存放在存放在ESP寄存器中的数据，寄存器中存放着数据、地址和函数传递的中间结果。Kruskal算法在调用寄存器中的整型数据，对边上的权值进行冒泡排序，将权值小的边放在数组的上面，然后在进行一次循环打印，循环过程