地图着色课程设计汇本汇本

《地图着色课程设计汇本汇本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计课程设计说明书地图着色学院：计算机与控制工程学院专业：计算机科学与技术学生姓名：xxxxx学号：成绩学生姓名：xxxxx学号：成绩指导教师：内容提要此题为地图着色问题，由地图着色问题很容易想到图的着色问题，因此可以把地图抽象为无向图来解决地图的着色问题。对地图的抽象相当于对图的抽象，即以邻接矩阵来实现地图的区域相邻的描绘，而对地图的区域数即以图的顶点数来描绘。设计说明书的内容包括需求分析，概要设计，详细设计，代码实现，后期测试等内容，需求分析是对此问题所需要实现的功能的介绍，概要设计

2、是对所需要实现功能的模块划分，以及初步的实现思想，详细设计通过编写大致的代码来实现功能，代码实现则是具体的解决问题，解决此问题设计了两个算法，贪心，回溯，在程序的测试阶段，回溯算法对同一个问题的解决速率高于贪心算法，但是结果都是以最少的颜色数来染色。课题实现的环境是在window环境下的eclipse中，通过在其中输入地图的区域数，图的连接情况，来选择相应的算法来实现染色，本次课题所采用的数据结构主要是二维数组来抽象图的邻接矩阵。目录1引言（或绪论）………………………………………………………………

3、……12需求分析…………………………………………………………………………22.1问题分析………………………………………………………………………22.3问题解决……………………………………………………………………22.3运行环境及开发工具…………………………………………………………32.4功能需求………………………………………………………………………32.4.1地图的抽象及输入…………………………………………………………32.4.2地图着色的算法设计………………………………………………………32.4

4、.3界面设计……………………………………………………………………32.4.4输出设计……………………………………………………………………32.5任务分配………………………………………………………………………43概要设计…………………………………………………………………………43.1数据定义………………………………………………………………………43.2功能模块定义…………………………………………………………………43.2.1地图的抽象输入模块………………………………………………………43.2.2输出

5、模块……………………………………………………………………43.2.3地图染色模块………………………………………………………………43.2.4界面设计模块………………………………………………………………53.2.5主模块………………………………………………………………………53.3程序流程图……………………………………………………………………64详细设计………………………………………………………………………74.1地图输入模块…………………………………………………………………74.1.1数据类型……

6、………………………………………………………………74.1.2具体实现……………………………………………………………………74.2界面设计模块…………………………………………………………………74.2.1数据类型……………………………………………………………………74.2.2具体实现……………………………………………………………………74.3算法设计模块…………………………………………………………………94.3.1回溯法过程…………………………………………………………………94.3.2贪心法过程……

7、………………………………………………………….105程序设计模块…………………………………………………………………115.1界面设计代码………………………………………………………………115.2染色实现模块………………………………………………………………156程序测试………………………………………………………………………196.1运行结果……………………………………………………………………196.2贪心、回溯着色结果及分析…………………………………………………197算法时间、空间复杂度分析…………

8、………………………………………227.1递归回溯……………………………………………………………………227.2贪心算法……………………………………………………………………228课设总结…………………………………………………………………………228.1已实现功能及不足…………………………………………………………228.2心得体会……………………………………………………………………22参考文献…………………………………………………………………………241引言（或绪论）此次课程设计的要求