数据结构课程设计-最小生成树

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

1、数据结构课程设计报告最小生成树数据结构课程设计报告设计题目：最小生成树专业：xxxxxx院系：计算机学院姓名：xxxxxxxxx学号：xxxxxx时间：2013年10月7日-16-数据结构课程设计报告最小生成树目录一、设计目的……………………………………………………………….-2-二、算法思想分析………………………………………………………-2-1.算法思想………………………………………………………………..-3-1）普里姆（Prim）算法思想……………………………………………………….-3-2）克鲁斯卡尔（Kruskal）算法

2、思想..........................................-3-2.系统采用的数据结构和算法………………………………-3-三、算法的描述与实现……………………………………………….-4-四、用户手册………………………………………………………………-7-五、总结…………………………………………………………………….-10-六、参考文献…………………………………………………………….-10-七、附录（源代码）………………………………………………...-10--16-数据结构课程设计报告最小生成树[摘要

3、]选择一颗生成树，使之总的消费最少，也就是要构造连通网的最小代价生成树（简称为最小生成树）的问题，一颗生成树的代价就是树上各边的代价之和，构造最小生成树可以有多种算法，其中多数算法利用了MST的性质。关键词：最小生成树连通图普里姆算法克鲁斯卡尔算法MST一、设计目的1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养

4、软件工作者所应具备的科学的工作方法和作风。二、算法思想分析该设计的要求是在n个城市之间建设网络，不仅要保证连通，还要求是最经济的架设方法。根据克鲁斯卡尔和普里姆算法的不同之处，该程序将城市个数大于十个时应用普里姆算法求最小生成树，而城市个数小于十个时则应用克鲁斯卡尔进行计算。-16-数据结构课程设计报告最小生成树1.算法思想1)普里姆（Prim）算法思想a)选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列；b)在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将

5、该边相关联的节点出列；c)重复b)直到所有的节点出列。2)克鲁斯卡尔（Kruskal）算法思想为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。由于生成树上不允许有回路，因此并非每一条居当前最小的边都可选。从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加

6、入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通，由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。2.系统采用的数据结构和算法1)数据结构TypedefintVertextype;Typedefintadimatrix[MaxVertexNum][MaxVertexNum];TypedefintVertextypevexlist[MaxVertexNum];TypedefintVexType;-16-数据结构课程设计报告最小生成树TypedefintAdjType;Typedefs

7、tructedgeElemedgeset[MaxVertexNum];structedgeElem{intfromvex;//头顶点intendvex;//尾顶点intweight;//权};Typedefstruct{intn;//图的顶点个数AdjTypeacrs[MAXVEX][MAXVEX];//边信息}GraphMatrix;Typedefstruct{intstart_vex,stop_vex;//边的起点和终点AdjTypeweight;//边的权}Edge;Edgemst[5];1)算法Great_adjmat

8、rix();Great_adjmatrix2();Kruskal();out_edgeaet();prim();二、算法的描述与实现-16-数据结构课程设计报告最小生成树1.Great_adjmatrix()和Great_adjmatrix2()是两种建立图的方法；2.克鲁斯