中国地图四色染色问题.docVIP

中国地图四色染色问题 问题描述 将中国地图用四种不同的颜色红、蓝、绿、黄来染色，要求相邻的省份染色不同， 问题分析 本文将中国地图的34个省、直辖市、自治区、特别行政区、、、行政区则问题转化为图论中的染色问题。由于海南、省不任何省份相邻，如果除海南、外如果n种染色方法，加上海南和台湾省后，4*4*n种染色方法。考虑除海南和台湾后的32的染色方法。地图染色方法 采用分开和台湾省的分析方法，的原因是除海南和台湾后的32，组成一个联通图，海南省和台湾省不和任何其它省份邻接。另一方面，建立一个联通图模型后，染色问题用深度优先遍历算法DFS，广度算法BFS解决，该方法的时间复杂度较高，暴力法，考虑两个省份可以减少计算机处理此问题的时间。采用DFS来解决这个染色问题。 3.1 简介 算法图的一种的深度遍历算法，即按照的地方遍历一个图，到一个分支的尽头，返回到最近一个未被遍历的结点，深度遍历。 的具体步骤可为下： 所有结点为“未”标记。 起始结点，标记为“访问”标记 始结点入栈 若栈为空，；若栈不为空，栈顶元素，该元素存在未被访问的顶点，输出一个邻接顶点，置为“访问”状态，；，元素退出栈顶。 3.2 中的DFS算法设计 我们先对结点染色，用从该结点出发，遍历该图，的下一结点颜色染为与之相邻的结点不同的颜色即可。该结点无法染色则回到上一个结点重新染色，所有的结点都被染色即可。统计染色种数。 问题的算法代码描述如下： _DFS(当前染色结点): i in 所有颜色 { while j的已染色邻接点 j相邻点被染i颜色 并break标记 { 当前结点为i if 当前结点为最后一个结点 else color_DFS(next) ｝ } 3.3 数据结构设计实现DFS染色算，需要设计的数据结构。图的结点不多，只有32，采用图的邻接矩阵来存储该图，为map[33][33]，ma[0]不存储数据，两结点i相邻，[i][j]=1，否则[i][j]=0。 便于计算机编程，将每一个地名用相应结点号表示，1：2:西藏,3:青海,4:甘肃,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。 地，颜色我们也可以用一个数字来表示，在这里，数字来代表颜色，比如1-2-蓝、3-绿、4-黄。 语言代码实现 #include stdio.h #include iostream using namespace std; int map[33][33]; int vis[33]; int n,m; long long cnt;//染色方法设置为long long防止溢出 void init_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]=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; map[4][13]=map[13][4]=1; map[4][27]=map[27][4]=1; map[5][6]=map[6][5]=1; map[5][7]=map[7][5]=1; map[5][8]=map[8][5]=1; map[5][9]=map[9][5]=1; map[5][10]=map[10][5]=1; map[5][12]=map[12][5]=1; map[5][13]=map[13][5]=1; map[6][13]=map[13][6]=1; map[7][8]=map[8][7]=1; map[8][9]=map[9][8]=1; map[9][10]=map[10][9]=1; map[10][11]=map[11][10]=1; map[10][12]=map[12][10]=1;