一、介绍
对地图的着色问题，能否用四个颜色对地图着色，要求每个相邻的区域都要着上不同的颜色。
二、算法思路
例如中国的省份为例，从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。
递归求解；在前面的n-1个节点都合法的着色之后，开始对第n个节点着色。这时候枚举可用的4个颜色（4着色），通过和与它相邻的节点的颜色相比较，来判断这个颜色是否合法。找到一种颜色能使第n个节点合法着色即可完成中国地图4着色。
三、代码
计算
安全
数据库
网络和加速
企业服务
#include <stdio.h>
//N=number of city + 1
#define N 8
int isOk(int metrix[N][N],int city[N],int current)
{
for(int j=0; j<current; j++)
if(metrix[current][j]==1&&city[j]==city[current])
return 0;
return 1;
}
void color(int metrix[N][N],int city[N],int sum,int current)
{
if(current<=sum)
for(int i=1; i<=4; i++) //colored current city
{
city[current]=i;
if(isOk(metrix,city,current))
{
color(metrix,city,sum,current+1); //colored next city
break;
}
}
}
int main()
{
int city[N]= {0};
int metrix[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(int i=0; i<N-1; i++)
printf("%3d",city[i]);
return 0;
}四、总结
这个代码有点简单，因为是事先输入了城市之间的关系。如果从实际角度考虑，应该要手动收入然后输出。最好还能够用图形化界面显示着×××况。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
