一、介绍

对地图的着色问题，能否用四个颜色对地图着色，要求每个相邻的区域都要着上不同的颜色。


二、算法思路

例如中国的省份为例，从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。

递归求解；在前面的n-1个节点都合法的着色之后，开始对第n个节点着色。这时候枚举可用的4个颜色（4着色），通过和与它相邻的节点的颜色相比较，来判断这个颜色是否合法。找到一种颜色能使第n个节点合法着色即可完成中国地图4着色。


三、代码

#include<stdio.h>//N=numberofcity+1#defineN8intisOk(intmetrix[N][N],intcity[N],intcurrent){for(intj=0;j<current;j++)if(metrix[current][j]==1&&city[j]==city[current])return0;return1;}voidcolor(intmetrix[N][N],intcity[N],intsum,intcurrent){if(current<=sum)for(inti=1;i<=4;i++)//coloredcurrentcity{city[current]=i;if(isOk(metrix,city,current)){color(metrix,city,sum,current+1);//colorednextcitybreak;}}}intmain(){intcity[N]={0};intmetrix[N][N]={{0,1,1,0,0,0,0},{1,0,0,1,0,1,0},{1,0,0,1,1,0,0},{0,1,1,0,1,1,0},{0,0,1,1,0,1,1},{0,1,0,1,1,0,1},{0,0,0,0,1,1,0}};printf("总共有%d个城市\n",N-1);color(metrix,city,N-1,0);printf("\n着色方法:\n");for(inti=0;i<N-1;i++)printf("%3d",city[i]);return0;}


四、总结

这个代码有点简单，因为是事先输入了城市之间的关系。如果从实际角度考虑，应该要手动收入然后输出。最好还能够用图形化界面显示着×××况。