图遍历与最小生成树实现.doc

数学与计算机学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:题目:图的遍历和最小生成树年级/专业/班:2011级软工一班学生姓名:学号:开始时间:2012年12月24日完成时间:2012年1月3日课程设计成绩:学与实际能力(20)创新(5)说明书(计算书、图纸、分析报告)撰写质量(45)总分(100)指导教师签名:年月日目录(小三黑体,居中)引言……………………………………………………………………………11需求分析……………………………………………………………………2概要设计……………………………………………………………………3详细设计……………………………………………………………………4调试分析……………………………………………………………………5用户使用说明………………………………………………………………6测试结果……………………………………………………………………7结论………………………………………………………………………致谢……………………………………………………………………………参考文献………………………………………………………………………(目录左对齐,,未具体指明使用字体的均为小四宋体,以下同)(目录中最多放二级标题。注意看页面的规范要求。尤其注意页眉。页眉从目录开始)摘要图是一种比线形表和树更为复杂的数据结构。在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法,邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词:图;存储结构;遍历引言数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合。利用数据结构能解决许多实际问题,在各个方面都有非常不错的成就。通过本项课程设计,培养学生独立思考、综合运用所学有关相应知识的能力,使学生巩固《数据结构》课程学习的内容,掌握工程软件设计的基本方法,强化上机动手编程能力,闯过理论与实践相结合的难关;为了培养学生综合运用所学知识、独立分析和解决实际问题的能力,培养创意识和创新能力,使学生获得科学研究的基础训练。为后续各门计算机课程的学习和毕业设计打下坚实基础。同时,可以利用这次机会来检验自己的c++数据结构水平,提高自己的写作水平,锻炼自己的动手能力。而此次课程设计的任务和意义在于:增强自己的动手能力,利用VC++,以及最小生成树算法,增强自己的调试程序和测试程序的能力。;程序处理输入数据,以十字链表,邻接矩阵和邻接链表的形式输出;根据已建成的图,程序实现图的深度优先遍历,广度优先遍历;显示图的最小生成树,连同分量的实现;采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。:66abcdefab2ae6ad5bd4bc1bf3邻接链表测试数据:78abcdefgabaeacafbgbddgcf十字链表测试数据:{数据对象:V{具有相同特征的数据元素,即V顶点集}数据关系:E={VR}VR={<v,w>|v,w∈V,<>表示顶点v和顶点w之间的边;}基本操作:初始化空图;输入建立图;广度优先遍历;深度优先遍历;最小生成树;},主要可以分为一下三个大的模块:邻接矩阵存储结构;邻接链表存储结构;十字链表存储结构;其中每个模块又包涵其它相应的子功能模块。 各功能模块(四号黑体)(AdjMWGraph)类中voidkruscal_arc();//克鲁斯卡尔算法AdjMWGraph(); //构造函数voidCreatG(intn,inte);//建立一个图的邻接矩阵voidDepthF();//连通分量的实现voidBoradF();//连通分量的实现voidPrintOut();//输出图的信息voidPrim();//普里姆算法voidkruscal_arc();//克鲁斯卡算法voidDepthM();//深度非递归优先遍历voidBorad(intv,intvisited[]);//广度非递归优先遍历voidDepth(intv,intvisited[]);//(AdjTWGraph)类中