理論上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)
{/*ok函數和下面的go函數和原來的壹樣,保留用來比較兩種算法*/
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)/*城市號從1開始編號,故跳過0編號*/
continue;
else
for(j=0;j<4;j++)
{
r_color[i]=allcolor[j];/*選取下壹種顏色,根據allcolor中顏色順序不同,結果不同*/
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;
/* clrscr();*/
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]);
}
說是人性化著色,其實還有壹個問題沒有考慮,那就是操作員跳躍式著色,就像大家玩“掃雷”遊戲壹樣。其實也容易實現,可以像定義選色順序壹樣定義著色順序。