1、C+和数据结构课程设计题目名称： 地图着色问题 姓 名 学 号 专 业 班 级 指导教师 编写日期 2017.7.1 第 1 页 共 十三 页2、 目录（1）问题描述.2（2）系统设计.4（3）源代码清单.7（4）运行结果测试与分析.10（5）结论与心得.12第 2 页 共 十三 页三、正文部分1、问题描述（1）题目：设计地图着色软件，对湖南省地图中的地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。（2）题目分析：由地图着色问题很容易想到图的着色问题，因此可以把地图抽象为无向图来解决地图的着色问题。题目以湖南省地图为实际应用载体，其本质是图着色问题（Graph Color
2、ing Problem, GCP）又称着色问题，是最著名的 NP-完全问题之一。对地图的抽象相当于对图的抽象，即以邻接矩阵来实现地图的区域相邻的描绘，而对地图的区域数即以图的顶点数来描绘。具体是将湖南省各个地级市进行编号，然后利用无向图各个顶点之间的边来表示各省的相邻关系。地图着色问题与著名四色定理：四色定理是一个著名的数学定理：如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗简洁的说法是：每个地图都可以用不多于四种颜色来染色，而且不会有两个邻接的区域颜色相同。这就是著名的四色定理，由四色定理可以想到只需要四种颜色就可以为一
3、个区域的地图着上颜色，而且相邻区域的颜色不相同。第 3 页 共 十三 页（3）基本要求：地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻；设计着色算法，保证邻接点不是同一种颜色；演示程序以用户和计算机的对话方式进行。（4）问题解决：计算机中，图主要可以用两种方法表示：邻接矩阵和邻接链表。N 个顶点的邻接矩阵是一个 N*N 的布尔矩阵，图中的每一个顶点都由一行或者一列来表示，如果从第 i 个顶点和第 j 个顶点之间有边连接，则矩阵第 i 行，第 j 列的元素等于 1，如果没有边连接，则等于 0，这就是图的邻接矩阵表示，那么地图也可以抽象为一个图，其可以用邻接矩阵来进行模拟：
4、对于每一个地图， 我们可以把每一个区 区域或国家) 看作一个点， 而区与区之间的邻接关系看作点与点之间的连线。从而将地图抽象为一个图，然后就可以用邻接矩阵抽象。如下图：其邻接矩阵为：A B C D EA 0 1 1 0 0B 1 0 1 1 1C 1 1 0 0 1D 0 1 0 0 1E 0 1 1 1 1（5）目的：第 4 页 共 十三 页掌握图基本操作的实现方法，了解递归的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。2、系统设计（1）总体分析设计：已知湖南省地图，将各地级市进行编号，然后利用无向图顶点之间的边来表示各省的第 5 页 共 十三 页相邻关系，创
5、建图的操作，采用图状的逻辑结构，存储结构选用邻接矩阵。首先把 14 个地级市看成 14 个顶点，从选定的一号顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程以一个递归的过程进行，直到所有的顶点都处理完后结束着色。（2）数据结构的设计：typedef struct /定义图vextype vexsMAXedg; /存放边的矩阵adjtype arcsMAXedgMAXedg; /图的邻接矩阵int vnum,arcnum; /图的顶点数和边数Graph;（3）
6、给出如下湖南省地图，省份抽象为点，接壤抽象为有边相连。得到如下顶点的边关系：（注：a 为湘西土家族苗族自治州，b 为张家界市，c 为常德市，d 为岳阳市，e 为怀化市，f 为益阳市，g 为长沙市，h 为娄底市，i 为湘潭市，j 为邵阳市，k 为株洲市，l 为衡阳第 6 页 共 十三 页市，m 为永州市，n 为郴州市）a b 1a e 1b e 1b c 1e c 1c d 1c f 1d f 1d g 1e f 1f g 1e h 1e j 1h f 1h g 1h j 1h i 1h l 1g i 1i k 1g k 1i l 1j l 1k l 1j m 1m l 1第 7 页 共 十三 页k n 1l n 1m n 1（4）功能模块的划分及模块间调用关系：（5）着色模块：int colorsame(int s,Graph G)/判断这个颜色能不能满足要求int i,flag=0;for(i=1;iG.vnum)/递归出口output(G);exit(1);elsefor(i=1;i=N;i+)/对每一种色彩逐个测试colors=i;if(colorsame(s,G)=0)trycolor(s+1,G);/进行下一块的着色
