数据结构与算法分析2.doc

文档介绍：数据结构与算法分析算法设计报告书班级惠普测试学号姓名指导教师庞志永算法设计项目名称:(),并选择适当的编程语言在计算机上实现。()程序能够正常运行,计算结果正确,满足设计要求。.(仅供参考)()描述及输入原始数据模块()求解最小生成树模块()构造欧拉图模块()搜索欧拉回路模块()抄近路计算模块() 课题关键:在给定一系列城市和每对城市之间的距离的情况下,求解访问每一座城市一次并回到起始城市的最短回路。 解答本课题的思路:以最小生成树T求解旅游回路:复制树的每条边构建欧拉图,运用深度优先搜索寻找欧拉图的欧拉回路,而树的深度优先搜索序列与此欧拉回路相同,可用深度优先搜索算法优化求解欧拉回路和抄近路算法的过程。.运行结果及其相关描述要求实例中城市的数量在—之间。命令行输入此次实验验证个城市即为个顶点,(一)以二十个城市为例算法路径为(二)以五个城市为例算法路径:最短路径::-----.课程设计总结在求解关于图的问题时选择合适的数据结构存图对算法的时间空间复杂度有很大影响。满足三角不等式的TSP问题的最小生成树算法可在O(n²