地图着色问题C/C++

已知中国地图，请设计地图着色软件，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色最少。
【提示】
（1） 数据结构的设计：地图可以采用图的数据结构，每个省为一个节点，边表示对应的两个省相邻。
（2） 算法设计：设计着色算法，保证邻接点不是同一种颜色。
（3） 地图数据的输入采取从文件中读取。
（4） 结果输出方式可以采用图形方式或文本方式。
我说的是程序-= 思路我也有 遍历序列 递归-=

从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。
理论上4种颜色就够了.地图的四色问题嘛!
可能会有多组解。用递归（dfs)就可以输出所有解了。

地图着色算法C语言源代码
前面我写了一个地图着色（即四色原理）的C源代码。

写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：

＃i nclude <stdio.h>
#define N 21
int allcolor[4];

int ok(int metro[N][N],int r_color[N],int current)
{
int j;
for(j=1;j<current;j++)
if(metro[current][j]==1&&r_color[j]==r_color[current])
return 0;
return 1;
}

void go(int metro[N][N],int r_color[N],int sum,int current)
{
int i;
if(current<=sum)
for(i=1;i<=4;i++)
{
r_color[current]=i;
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1);
return;
}
}
}

void color(int metro[N][N],int r_color[N],int sum,int start)
{
int i,j,k;
r_color[start]=allcolor[0];
for(i=start+1;i!=start;i=(i+1)%(sum+1))
if(i==0)
continue;
else
for(j=0;j<4;j++)
{
r_color[i]=allcolor[j];
for(k=1;k<i;k++)
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;
if(k>=i)
break;
}
}

void main()
{
int r_color[N]={0};
int t_color[N]={0};
int i;
int start;
int metro[N][N]={{0},
{0,1,1,1,1,1,1},
{0,1,1,1,1},
{0,1,1,1,0,0,1},
{0,1,1,0,1,1},
{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};
allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;
start=1;

printf("\nAll color is:\n");
for(i=0;i<4;i++)
printf("%d ",allcolor[i]);
go(metro,r_color,20,1);
printf("\nFirst method:\n");
for(i=1;i<=20;i++)
printf("%3d",r_color[i]);
color(metro,t_color,20,start);
printf("\nSecond method:\n");
printf("\nAnd the start metro is:%d\n",start);
for(i=1;i<=20;i++)
printf("%3d",t_color[i]);
}

说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息