地圖四著色問題

一、介紹

    對地圖的著色問題，能否用四個顏色對地圖著色，要求每個相鄰的區(qū)域都要著上不同的顏色。

二、算法思路

例如中國的省份為例，從一個省開始，給它涂上任意一種顏色1，遍歷它旁邊的省份，涂上與已經(jīng)涂色并于他相鄰的省份不同的顏色就行了。

遞歸求解；在前面的n-1個節(jié)點都合法的著色之后，開始對第n個節(jié)點著色。這時候枚舉可用的4個顏色（4著色），通過和與它相鄰的節(jié)點的顏色相比較，來判斷這個顏色是否合法。找到一種顏色能使第n個節(jié)點合法著色即可完成中國地圖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個城市\(zhòng)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;
}

四、總結

    這個代碼有點簡單，因為是事先輸入了城市之間的關系。如果從實際角度考慮，應該要手動收入然后輸出。最好還能夠用圖形化界面顯示著×××況。