图的遍历与最小生成树的实现

《图的遍历与最小生成树的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法课程设计数学与计算机学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:题目:图的遍历和最小生成树年级/专业/班:2011级软工一班学生姓名:学　　号:开始时间:2012年12月24日完成时间:2012年1月3日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总分（100）指导教师签名：年月日数据结构与算法课程设计目录（小三黑体，居中）引言……………………………………………………………………………11需求分析……………………………………………………………………2概要设计

2、……………………………………………………………………3详细设计……………………………………………………………………4调试分析……………………………………………………………………5用户使用说明………………………………………………………………6测试结果……………………………………………………………………7结论………………………………………………………………………致谢……………………………………………………………………………参考文献………………………………………………………………………（目录左对齐，所有的均为1.5倍行距，未具体指明使用字体的均为小四宋体，以下同）(目录中

3、最多放二级标题。注意看页面的规范要求。尤其注意页眉。页眉从目录开始)数据结构与算法课程设计摘要图是一种比线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：图；存储结构；遍历数据结构与算法课程设计引言数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。利用数据结构能解决许多实际问题

4、，在各个方面都有非常不错的成就。通过本项课程设计，培养学生独立思考、综合运用所学有关相应知识的能力，使学生巩固《数据结构》课程学习的内容，掌握工程软件设计的基本方法，强化上机动手编程能力，闯过理论与实践相结合的难关；为了培养学生综合运用所学知识、独立分析和解决实际问题的能力，培养创意识和创新能力，使学生获得科学研究的基础训练。为后续各门计算机课程的学习和毕业设计打下坚实基础。同时，可以利用这次机会来检验自己的c++数据结构水平，提高自己的写作水平，锻炼自己的动手能力。而此次课程设计的任务和意义在于：增强自己的动手能力，利用VC++6.0等专业软件编程实现图各种遍历的

5、算法，以及最小生成树算法，增强自己的调试程序和测试程序的能力。1需求分析1.1任务与分析1.由键盘向程序输入相关数据；2.程序处理输入数据，以十字链表，邻接矩阵和邻接链表的形式输出；3.根据已建成的图，程序实现图的深度优先遍历，广度优先遍历；4.显示图的最小生成树，连同分量的实现；5.采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。1.2测试数据1.邻接矩阵测试数据：66abcdefab2ae6ad5bd4bc1bf32.邻接链表测试数据：78abcdefgabaeacafbgbddgcf3.十字链表测试数据：453225439934662概要设计数据

6、结构与算法课程设计2.1ADT描述ADTGraph{数据对象：V{具有相同特征的数据元素，即V顶点集}数据关系：E＝{VR}VR={

7、v,w∈V,表示顶点v和顶点w之间的边；}基本操作：初始化空图；输入建立图；广度优先遍历；深度优先遍历；最小生成树；}ADTGraph2.2程序模块结构根据本系统对功能实现的要求，主要可以分为一下三个大的模块：1.邻接矩阵存储结构；2.邻接链表存储结构；3.十字链表存储结构；其中每个模块又包涵其它相应的子功能模块。则根据以上可以得到本系统的概要设计图图的遍历与最小生成树退出系统十字链表存储结构邻接链表存储结构邻接矩

8、阵存储结构数据结构与算法课程设计2.3　各功能模块（四号黑体）2.3.1在邻接矩阵（AdjMWGraph）类中voidkruscal_arc();//克鲁斯卡尔算法AdjMWGraph();//构造函数voidCreatG(intn,inte);//建立一个图的邻接矩阵voidDepthF();//连通分量的实现voidBoradF();//连通分量的实现voidPrintOut();//输出图的信息voidPrim();//普里姆算法voidkruscal_arc();//克鲁斯卡算法voidDepthM();//深度非递归优先遍历voidBorad(intv