地圖著色算法C語言源代碼[原創(chuàng)] 
       前面我寫了一個地圖著色（即四色原理）的C源代碼。見http://bugeyes.blog.edu.cn/user1/20989/archives/2005/986232.shtml。

       寫完以后想了一下，感覺還不完善，因為從實際操作的角度來考慮，四種可用的顏色放在旁邊，不同的人可能會有不同的選擇順序，另外，不同的人可能會選擇不同的城市作為著色的起點，而當(dāng)時的程序沒有考慮這個問題。于是，把程序修改為下面的樣子，還請同行分析并指出代碼中的不足之處：

＃i nclude <stdio.h>
#define N 21
int allcolor[4];/*可用的顏色*/

int ok(int metro[N][N],int r_color[N],int current)
{/*ok函數(shù)和下面的go函數(shù)和原來的一樣,保留用來比較兩種算法*/
   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))/*把所有編號看作一個環(huán)*/
    if(i==0)/*城市號從1開始編號,故跳過0編號*/
       continue;
    else
     for(j=0;j<4;j++)
     {
        r_color[i]=allcolor[j];/*選取下一種顏色,根據(jù)allcolor中顏色順序不同，結(jié)果不同*/
        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;/*選色順序，順序不同，結(jié)果不同*/
   start=1;
/*   clrscr();*/
   printf("\nAll color is:\n");
   for(i=0;i<4;i++)/*當(dāng)前選色順序*/
      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]);
}

       說是人性化著色，其實還有一個問題沒有考慮，那就是操作員跳躍式著色，就像大家玩“掃雷”游戲一樣。其實也容易實現(xiàn)，可以像定義選色順序一樣定義著色順序。