地图染色算法详解


作者: 康凯森

日期: 2016-11-19

分类: 算法


本文写于我大一或大二时,今天整理时发现了就贴出来

小梦今天给大家分享一下栈的应用:利用栈的思想和回溯算法来解决地图染色问题

什么是回溯算法

其实很简单,说白了就是试探法,像走迷宫一样,我们不断向前走着试探,遇到死路了,标记下,再往回退一步,再选择其他路线前进,如果在碰壁了,就标记下,再返回,再选择其他路线继续向着终点前进,如此循环,直到走到终点。

什么是地图染色问题

就是用颜色去染地图上不同的行政区域,使得相邻的区域不同色即可。首先我们要解决的第一个问题是,我们最少使用多少种颜色就可以解决任意多块行政区域的染色。这个问题的答案,伟大的数学家已经告诉我们了,那就是只需四种颜色。这也就是所谓的四色定理。

选择什么数据结构来存储图

显而易见,由于地图本身的特点,我们首先会想到图的存储结构,又因为我们只关心图与图之间的相邻关系,所以我们选择图的邻接矩阵来存储图。这个很简单,如果i区域和j区域相邻,我们则对[i][j][j][i]赋值为1,若不相邻,则赋值为0. 例如下图:

此处输入图片的描述

其对应的邻接矩阵即为:

{
{0,1,1,1,1,1},
{1,0,1,1,0,0},
{1,1,0,1,1,1},
{1,0,1,0,0,1},
{1,1,1,0,0,1},
{1,0,1,1,1,0},
};

图的存储结构搞定了。颜色就很简单了,我们用1,2,3,4依次来代表红,蓝,绿,黄四种颜色。用栈s[i]来表示地图的区域的颜色序号,N表示地图的区域个数。

地图染色算法的基本思路

主要思想就是前面介绍的回溯思想

从第一个行政区域开始,依次用1,2,3,4对每个区域染色。如果当前区域的颜色和周围之前已经染色的每个区域颜色都不相同,则用是栈s[i]记下当前区域的颜色序号。如果和之前区域颜色重复,依次用下一个颜色进行试探。如果当前区域用1,2,3,4四种颜色染色均重色,则开始退栈回溯,修改当前栈顶颜色序号,再进行试探,如此这样循环,直到所有区域都染色成功。

地图染色算法代码

大一时的代码,注释和代码风格都很渣!

#include<stdio.h>

#define N 6 // N表示区域个数

int s[N];  //栈s[i]来表示地图的区域的颜色序号

void MapColor(int dist[N][N],int s[N])
{
int color,area,k,i;  //color代表颜色,area 表示当前要染色的是第几个区域,k表示已经染色区域的颜色
s[0]=1; //第一个区域先着色为颜色1
area=1;//从第二区域开始试探染色
color=1;//从第一种颜色开始试探
while(area<N)//是否全部染色完毕
{

while(color<=4)
{

k=0;//对每一个区域,都从第一个区域的颜色开始比较。
while((k<area)&&(s[k]*dist[area][k]!=color))//判断是否重色

//这个循环判定条件是整个算法的关键,理解了这个,整个算法就很easy了,所以小梦就啰嗦几句吧。  dist[area][k]表示当前即将染色区域和已经染色的第K个区域是否相邻。s[k]*dist[area][k] 若K区域和area区域相邻,则其表示当前第K个区域的颜色,若不相邻,则其值为0,则肯定不会重色,就可以将color复制给当前区域area的颜色s[k].解释的有些费劲,大家可以直接复制代码,运行一下,在对着图上的颜色跟着代码走几步就会理解了。
k++;
if(k<area)
color++;     //area 区域与K区域重色
else
{
s[area]=color;  //保存area区域的颜色
area++;     //准备颜色下一个区域
if(area>=N)
break;
color=1;  //每次都从第一个颜色开始试探
}
}
if(color>4)//area没有找到合适的颜色,需要进行回溯
{
area=area-1;  // 回溯并修改area-1域的颜色
color=s[area]+1;  //将预备颜色换为当前栈顶区域的下一个颜色
}

}

printf(“地图区域标号为1~6的染色情况为:\n”);
for(i=0;i<N;i++)
{
printf(“NO.%d:”,i+1);
switch(s[i])
{
case 0:printf(“WRONG MAP!\n”);break;
case 1:printf(“RED\n”);break;
case 2:printf(“BLUE\n”);break;
case 3:printf(“GREEN\n”);break;
case 4:printf(“YELLOW\n”);break;
default:printf(“什么的什么啊!1″);break;
}
}
}

int main()
{
int dist[N][N]={
{0,1,1,1,1,1},//地图的邻接矩阵
{1,0,1,1,0,0},
{1,1,0,1,1,1},
{1,0,1,0,0,1},
{1,1,1,0,0,1},
{1,0,1,1,1,0},
};
int s[N]={0};
MapColor(dist,s);
return 0;
}

评论