1、 算法分析与设计 课程设计说明书 地图着色 学 院： 计算机与控制工程学院 专 业： 计算机科学与技术 学生姓名：xxxxx 学号： 成绩 学生姓名：xxxxx 学号： 成绩 指导教师： 内 容 提 要 此题为地图着色问题，由地图着色问题很容易想到图的着色问题，因此可以 把地图抽象为无向图来解决地图的着色问题。对地图的抽象相当于对图的抽象， 即以邻接矩阵来实现地图的区域相邻的描绘， 而对地图的区域数即以图的顶点数 来描绘。设计说明书的内容包括需求分析，概要设计，详细设计，代码实现，后 期测试等内容，需求分析是对此问题所需要实现的功能的介绍，概要设计是对所 需要实现功能的模块划分，以及初步的实现
2、思想，详细设计通过编写大致的代码 来实现功能， 代码实现则是具体的解决问题， 解决此问题设计了两个算法， 贪心， 回溯，在程序的测试阶段，回溯算法对同一个问题的解决速率高于贪心算法，但 是结果都是以最少的颜色数来染色。 课题实现的环境是在 window 环境下的 eclipse 中，通过在其中输入地图的 区域数，图的连接情况，来选择相应的算法来实现染色，本次课题所采用的数据 结构主要是二维数组来抽象图的邻接矩阵。 目 录 1 引言 （或绪论） 1 2 需求分析2 2.1 问题分析 2 2.3 问题解决2 2.3 运行环境及开发工具3 2.4 功能需求 3 2.4.1 地图的抽象及输入 3 2.
3、4.2 地图着色的算法设计 3 2.4.3 界面设计 3 2.4.4 输出设计 3 2.5 任务分配 4 3 概要设计 4 3.1 数据定义 4 3.2 功能模块定义 4 3.2.1 地图的抽象输入模块 4 3.2.2 输出模块 4 3.2.3 地图染色模块 4 3.2.4 界面设计模块 5 3.2.5 主模块 5 3.3 程序流程图 6 4 详细设计 7 4.1 地图输入模块 7 4.1.1 数据类型 7 4.1.2 具体实现 7 4.2 界面设计模块 7 4.2.1 数据类型 7 4.2.2 具体实现 7 4.3 算法设计模块 9 4.3.1 回溯法过程9 4.3.2 贪心法过程.10 5 程序设计模块11 5.1 界面设计代码11 5.2 染色实现模块15 6 程序测试19 6.1 运行结果19 6.2 贪心、回溯着色结果及分析19 7 算法时间、空间复杂度分析22 7.1 递归回溯
