中国地图四色染色问题

《中国地图四色染色问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国地图四色染色问题一、问题描述将中国地图用四种不同的颜色红、蓝、绿、黄来染色，要求相邻的省份染色不同，有多少种不同的方案？二、问题分析本文将中国地图的34个省、直辖市、自治区、以及特别行政区转化为图论中的图模型。其中每个省、市、自治区、特别行政区用图中的一个结点表示，两个结点间联通仅当两个板块接壤。则问题转化为图论中的染色问题。由于海南、台湾省不与其它任何省份相邻，所以如果除海南、台湾外如果有n种染色方法，那么加上海南和台湾省后，有4*4*n种染色方法。下面考虑除海南和台湾后的32个结点的染色方法。三、中国地图染色方法采用分开海南和台湾

2、省的分析方法，一方面的原因是除海南和台湾后的32个结点，可以组成一个联通图，因为海南省和台湾省不和任何其它省份邻接。另一方面，我们建立一个联通图模型后，染色问题可以用深度优先遍历算法DFS，或者广度优先遍历算法BFS来解决，由于该方法的时间复杂度较高，属于暴力法，少考虑两个省份可以减少计算机处理此问题的时间。本文采用DFS算法来解决这个染色问题。3.1DFS算法简介DFS算法是图的一种图的深度遍历算法，即按照往深的地方遍历一个图，若到一个分支的尽头，则原路返回到最近一个未被遍历的结点，继续深度遍历。DFS遍历的具体步骤可为下：1）标记图中

3、所有结点为“未访问”标记。2）输出起始结点，并标记为“访问”标记3）起始结点入栈4）若栈为空，程序结束；若栈不为空，取栈顶元素，若该元素存在未被访问的邻接顶点，则输出一个邻接顶点，并置为“访问”状态，入栈；否则，该元素退出栈顶。3.2染色问题中的DFS算法设计我们先对任一结点染色，然后用DFS从该结点出发，遍历该图，遍历的下一结点颜色染为与之相邻的结点不同的颜色即可。如果该结点无法染色则回到上一个结点重新染色，直到所有的结点都被染色即可。最后统计染色种数。染色问题的算法伪代码可以描述如下：color_DFS(当前染色结点):foriin所

4、有颜色{whilej的已染色邻接点if结点j相邻接点被染成i颜色标记并breakif未被标记{当前结点染为i色if当前结点为最后一个结点endelsecolor_DFS(next)｝}3.3数据结构设计为了实现DFS染色算法，我们需要设计相应的数据结构。由于图的结点不多，只有32个，我们采用图的邻接矩阵来存储该图，记为map[33][33]，map[0]不存储数据，如果两结点i，j相邻，map[i][j]=1，否则map[i][j]=0。为了便于计算机编程，我们将每一个地名用相应结点号来表示，1："新疆",2:"西藏",3:"青海",4:

5、"甘肃",5:"内蒙古",6:"宁夏",7:"黑龙江",8:"吉林",9:"辽宁",10:"河北",11:"北京",12:"山西",13:"陕西",14:"山东",15:"天津",16:"河南",17:"安徽",18:"江苏",19:"上海",20:"浙江",21:"福建",22:"江西",23:"广东",24:"湖南",25:"湖北",26:"重庆",27:"四川",28:"贵州",29:"云南",30:"广西",31:"香港",32:"澳门"。新疆和西藏相邻，那么我们就可以用map[1][2]=1来表示。同样地，一种颜色我们也可以用一

6、个数字来表示，在这里，我们用数字来代表颜色，比如1-红、2-蓝、3-绿、4-黄。一、C语言代码实现#include#includeusingnamespacestd;charname[][10]={"","新疆","西藏","青海","甘肃","内蒙古","宁夏","黑龙江","吉林","辽宁","河北","北京","山西","陕西","山东","天津","河南","安徽","江苏","上海","浙江","福建","江西","广东","湖南","湖北","重庆","四川","贵州","云南","广西"

7、,"香港","澳门"};charcolor[][4]={"","红","蓝","绿","黄"};intmap[33][33];intvis[33];intn,m;longlongcnt;//染色方法设置为longlong防止溢出voidinit_map(){map[1][2]=map[2][1]=1;//表示新疆和西藏连通map[1][3]=map[3][1]=1;map[1][4]=map[4][1]=1;map[2][3]=map[3][2]=1;map[2][27]=map[27][2]=1;map[2][29]=map[29][2

8、]=1;map[3][4]=map[4][3]=1;map[3][27]=map[27][3]=1;map[4][5]=map[5][4]=1;map[4][6]=map[6][4]=1;ma