地图染色问题可以根据四色定理来解决。所谓四色定理，就是指可以用不多于四种的颜色对地图着色，使相邻的行政区域不重色，因此我们可以用四色定理的结论，用回溯算法对一幅给定的地图染色。
算法的基本思想是：从第(1)号行政区域开始染色，每个区域逐次用颜色1#、2#、3#、4#进行试探，若当前所取的颜色与周围已染色的行政区域不重色，则用栈记下该区域的颜色序号，否则依次用下一颜色进行试探；若出现用1#到4#颜色均与相邻区域的颜色重色，则需退栈回溯，修改当前栈顶的颜色序号，再进行试探。直到所有行政区域都已分配合适的颜色。
行政地图如下：
具体程序实现如下：
#include<stdio.h>
#define N 7//区域个数
void MapColor(int dist[N][N],int s[N])
{
int color,area,k;//总共有4种颜色
s[0]=1;//第一个区域先着色为颜色1
area=1;//从第二区域开始试探染色
color=1;//从第一种颜色开始试探
while(area<N)//是否全部染色完毕
{
while(color<=4)
{
if(area>=N)
break;
k=0;
while((k<area)&&(s[k]*dist[area][k]!=color))//判断是否重色
k++;
if(k<area)
color++;
else
{
s[area]=color;
area++;
color=1;
}
}
if(color>4)//没有找到合适的颜色，需要进行回溯
{
area=area-1;
color=s[area]+1;
}
}
}
void main()
{
int dist[N][N]={{0,1,1,1,1,1,0},//地图的邻接矩阵
{1,0,0,0,0,1,0},
{1,0,0,1,1,0,0},
{1,0,1,0,1,1,0},
{1,0,1,1,0,1,0},
{1,1,0,1,1,0,0},
{0,0,0,0,0,0,0}};
int s[N]={0};
MapColor(dist,s);
printf("地图区域标号为1~7的染色情况为：");
for(int i=0;i<N;i++)
printf("%d ",s[i]);
printf("\n");
}
结果显示如下：
其中栈S的变化情况如下：
注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接： 解释说明
原文：http://blog.csdn.net/tengweitw/article/details/17641017
作者：nineheadedbird
