19-图的遍历和生成树求解实现

《19-图的遍历和生成树求解实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机科学与技术本科专业数据结构课程设计任务书题目：图的遍历和生成树求解实现学生姓名：学号：班级：题目类型：软件工程（R）指导教师：张其文一．题目简介很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求学生写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。二．主要任务第一部分：基本算法实现1、线性结构基

2、本算法实现（指导老师根据题目指定）；2、树型结构基本算法实现（指导老师根据题目指定）；3、图型结构基本算法实现（指导老师根据题目指定）；4、查找基本算法实现（指导老师根据题目指定）；5、排序基本算法实现（指导老师根据题目指定）；第二部分：指定题目的设计与实现1、查阅文献资料，一般在3篇以上；2、设计图遍历的演示过程，建立数据的逻辑结构和物理结构；3、完成相应算法的设计；4、完成测试工作；5、撰写设计说明书；6、做好答辩工作。一．主要内容、功能及技术指标（1）使用邻接矩阵（或邻接表）存储结构实现数据的输入（图存储结构的建立）、深度优先和广度优先遍历、并输出原图结构及遍历结

3、果、最小生成树（最小代价生成树）等功能；（2）设图的结点不超过10个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n，以此作为测试数据，以用户指定的结点为起点，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；（3）算法对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足规格说明要求的结果，例：测试边界数据，如单个结点；对算法实现过程中的异常情况能给出有效信息；（4）较高要求：实现图形化操作界面，用动画过程演示。二．提交的成果1.设计说明书一份，内容包括：1)中文摘要100字；关键词3-5个；2)序言；3）采用类c语言定义相

4、关的数据类型4）各模块流程图及伪码算法5）函数的调用关系图6）调试分析a、调试中遇到的问题及对问题的解决方法；b、算法的时间复杂度和空间复杂度。7）测试结果8）源程序（带注释）9)设计总结、参考文献、致谢等。2.刻制光盘一张。一．主要参考文献1严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.2严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.3《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社（影印版）.4谭浩强.《c语言程序设计》.清华大学出版社.5．数据结构与算法分析（Java版）,AP

5、racticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,张铭,刘晓丹译 电子工业出版社2001年1月2012年5月18日