? ? ?任何平面地圖可以使用4種顏色給每個不同的城市著色，而保證相鄰的城市著不同的顏色。

? ? 回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法。回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。

? ? 把地圖上的每個州抽象為一個點，并給每個州編號，相鄰的州之間用直線連接。據(jù)此做出鄰接矩陣，若第i個城市與第j個城市相鄰，則a[i][j]=1,否則a[i][j]=0。

按照編號從小到大的順序檢查每個城市，對每個城市從1開始使用4種顏色著色，若當(dāng)前顏色可用（即不與相鄰州顏色相同），則著色；否則測試下一種顏色。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

#include<iostream> #include<iomanip> #include <string> using namespace std; int N;//選擇顏色個數(shù) int color[8]={0};//存儲對應(yīng)塊對應(yīng)顏色 typedef struct//定義圖 {string state[50]; //各州的名稱int a[50][50]; //相鄰州的鄰接矩陣int vnum,arcnum;//圖的頂點數(shù)和邊數(shù) }Graph;//輸出顏色信息 void inforc() {cout<<"1.紅色 2.藍(lán)色 3.黃色 4.粉色 ";if(N>=5) cout<<"5.綠色 ";if(N>=6) cout<<"6.橙色 ";if(N>=7) cout<<"7.白色 ";cout<<endl<<endl;}//輸入地圖的信息 void CreateGraph(Graph &G) {G.vnum=50;G.arcnum=233;//初始化矩陣for(int i=0;i<50;i++)for(int j=0;j<50;j++)G.a[i][j]=0;G.state[0] = "華盛頓州";G.state[1] = "俄勒岡州";G.state[2] = "加利福尼亞州";G.state[3] = "愛達(dá)荷州";G.state[4] = "內(nèi)華達(dá)州";G.state[5] = "蒙他拿州";G.state[6] = "猶他州"; G.state[7] = "亞利桑那州";G.state[8] = "懷俄明州";G.state[9] = "科羅拉多州";G.state[10] = "新墨西哥州";G.state[11] = "北達(dá)科他州";G.state[12] = "南達(dá)科他州";G.state[13] = "內(nèi)布拉斯加州";G.state[14] = "堪薩斯州";G.state[15] = "俄克拉荷馬州";G.state[16] = "德克薩斯州";G.state[17] = "明尼蘇達(dá)州";G.state[18] = "愛荷華州";G.state[19] = "密蘇里州";G.state[20] = "阿肯色州";G.state[21] = "路易斯安那州";G.state[22] = "威斯康星州";G.state[23] = "伊利諾斯州";G.state[24] = "密歇根州";G.state[25] = "印第安納州";G.state[26] = "俄亥俄州";G.state[27] = "肯塔基州";G.state[28] = "田納西州";G.state[29] = "密西西比州";G.state[30] = "阿拉巴馬州";G.state[31] = "佐治亞州";G.state[32] = "佛羅里達(dá)州";G.state[33] = "紐約";G.state[34] = "賓夕法尼亞州";G.state[35] = "西弗吉尼亞州";G.state[36] = "弗吉尼亞州";G.state[37] = "北卡羅來納州";G.state[38] = "南卡羅來納州";G.state[39] = "緬因州";G.state[40] = "新罕布什爾州";G.state[41] = "佛蒙特州";G.state[42] = "馬薩諸塞州";G.state[43] = "羅德島州";G.state[44] = "康涅狄格州";G.state[45] = "新澤西州";G.state[46] = "德拉華州";G.state[47] = "馬里蘭州";G.state[48] = "阿拉斯加州";G.state[49] = "夏威夷州";G.a[0][1]=1;G.a[0][3]=1;G.a[1][0]=1; G.a[1][2]=1;G.a[1][3]=1;G.a[1][4]=1;G.a[2][1]=1;G.a[2][4]=1;G.a[2][7]=1;G.a[3][0]=1;G.a[3][1]=1;G.a[3][4]=1; G.a[3][5]=1;G.a[3][6]=1;G.a[3][8]=1;G.a[4][1]=1;G.a[4][2]=1;G.a[4][3]=1;G.a[4][6]=1;G.a[4][7]=1;G.a[5][3]=1; G.a[5][8]=1;G.a[5][11]=1;G.a[5][12]=1;G.a[6][3]=1;G.a[6][4]=1;G.a[6][7]=1;G.a[6][8]=1;G.a[6][9]=1;G.a[7][2]=1; G.a[7][4]=1;G.a[7][6]=1;G.a[7][9]=1;G.a[7][10]=1;G.a[8][3]=1;G.a[8][5]=1;G.a[8][6]=1;G.a[8][9]=1;G.a[8][12]=1;G.a[8][13]=1;G.a[9][6]=1;G.a[9][7]=1;G.a[9][8]=1;G.a[9][10]=1;G.a[9][13]=1;G.a[9][14]=1;G.a[10][7]=1;G.a[10][9]=1;G.a[10][14]=1;G.a[10][15]=1;G.a[10][16]=1;G.a[11][5]=1;G.a[11][12]=1;G.a[11][17]=1;G.a[12][5]=1;G.a[12][8]=1;G.a[12][11]=1;G.a[12][13]=1;G.a[12][17]=1;G.a[12][18]=1;G.a[13][8]=1;G.a[13][9]=1;G.a[13][12]=1;G.a[13][14]=1;G.a[13][18]=1;G.a[14][9]=1;G.a[14][10]=1;G.a[14][13]=1;G.a[14][15]=1;G.a[14][18]=1;G.a[14][19]=1;G.a[15][10]=1;G.a[15][14]=1;G.a[15][16]=1;G.a[15][19]=1;G.a[15][20]=1;G.a[16][10]=1;G.a[16][15]=1;G.a[16][20]=1;G.a[16][21]=1;G.a[17][11]=1;G.a[17][12]=1;G.a[17][18]=1;G.a[17][22]=1;G.a[17][24]=1;G.a[18][12]=1;G.a[18][13]=1;G.a[18][14]=1;G.a[18][17]=1;G.a[18][19]=1;G.a[18][22]=1;G.a[18][23]=1;G.a[19][14]=1;G.a[19][15]=1;G.a[19][18]=1;G.a[19][20]=1;G.a[19][23]=1;G.a[20][15]=1;G.a[20][16]=1;G.a[20][19]=1;G.a[20][21]=1;G.a[20][28]=1;G.a[20][29]=1;G.a[21][16]=1;G.a[21][20]=1;G.a[21][29]=1;G.a[22][17]=1;G.a[22][18]=1;G.a[22][23]=1;G.a[22][24]=1;G.a[23][18]=1;G.a[23][19]=1;G.a[23][22]=1;G.a[23][25]=1;G.a[23][27]=1;G.a[24][17]=1;G.a[24][22]=1;G.a[24][25]=1;G.a[24][26]=1;G.a[25][23]=1;G.a[25][24]=1;G.a[25][26]=1;G.a[25][27]=1;G.a[26][24]=1;G.a[26][25]=1;G.a[26][27]=1;G.a[26][34]=1;G.a[26][35]=1;G.a[27][23]=1;G.a[27][25]=1;G.a[27][26]=1;G.a[27][28]=1;G.a[27][35]=1;G.a[27][36]=1;G.a[28][20]=1;G.a[28][27]=1;G.a[28][29]=1;G.a[28][30]=1;G.a[28][31]=1;G.a[28][36]=1;G.a[28][37]=1;G.a[29][20]=1;G.a[29][21]=1;G.a[29][28]=1;G.a[29][30]=1;G.a[30][28]=1;G.a[30][29]=1;G.a[30][31]=1;G.a[31][28]=1;G.a[31][30]=1;G.a[31][32]=1;G.a[31][37]=1;G.a[31][38]=1;G.a[32][31]=1;G.a[33][34]=1;G.a[33][41]=1;G.a[33][42]=1;G.a[33][44]=1;G.a[33][45]=1;G.a[34][26]=1;G.a[34][33]=1;G.a[34][35]=1;G.a[34][45]=1;G.a[34][46]=1;G.a[34][47]=1;G.a[35][26]=1;G.a[35][27]=1;G.a[35][34]=1;G.a[35][36]=1;G.a[35][46]=1;G.a[36][27]=1;G.a[36][28]=1;G.a[36][35]=1;G.a[36][37]=1;G.a[36][46]=1;G.a[37][28]=1;G.a[37][31]=1;G.a[37][36]=1;G.a[37][38]=1;G.a[38][31]=1;G.a[38][37]=1;G.a[39][40]=1;G.a[39][41]=1;G.a[40][39]=1;G.a[40][41]=1;G.a[40][42]=1;G.a[41][33]=1;G.a[41][39]=1;G.a[41][40]=1;G.a[41][42]=1;G.a[42][33]=1;G.a[42][40]=1;G.a[42][41]=1;G.a[42][43]=1;G.a[42][44]=1;G.a[43][42]=1;G.a[43][44]=1;G.a[44][33]=1;G.a[44][42]=1;G.a[44][43]=1;G.a[44][45]=1;G.a[45][33]=1;G.a[45][34]=1;G.a[45][44]=1;G.a[45][47]=1;G.a[46][34]=1;G.a[46][35]=1;G.a[46][36]=1;G.a[46][47]=1;G.a[47][34]=1;G.a[47][45]=1;G.a[47][46]=1;}//輸出地圖的信息 void PrintGraph(Graph G) {int i,j;cout<<"美國的50個州：\n";cout<<endl;for(i=0;i<G.vnum;i++){if(i%3==0&&i!=0) cout<<endl;cout<<setw(2)<<left<<i<<"."<<setw(15)<<left<<G.state[i];}cout<<endl<<endl;cout<<"互相接壤的國家(地圖的鄰接矩陣)：\n";cout<<endl;for(i=0;i<G.vnum;i++)for(j=0;j<G.vnum;j++)if(G.a[i][j]==1)cout<<G.state[i]<<"與"<<G.state[j]<<"接壤 "<<endl;cout<<endl;}//顏色比對函數(shù) int colorsame(int s,Graph G)//限定函數(shù) {int i,flag=0; //初始化標(biāo)志位為零for(i=0;i<s;i++)//與已經(jīng)涂過色的州進(jìn)行比對if(G.a[i][s]==1&&color[i]==color[s])//兩州接壤且顏色相同{flag=1;break;}//標(biāo)志為一，在trycolor函數(shù)中更換顏色return flag; //返回標(biāo)志值 }//輸出函數(shù) void output(Graph G) {for(int i=0;i<G.vnum;i++){if(i%3==0&&i!=0) cout<<endl;cout.setf(ios::left); cout<<setw(2)<<i<<"."<<setw(15)<<G.state[i]<<":";//相應(yīng)州名switch(color[i]) //將數(shù)字轉(zhuǎn)換成相應(yīng)顏色{case 0: cout<<" 紅 ";break;case 1: cout<<" 藍(lán) ";break;case 2: cout<<" 黃 ";break;case 3: cout<<" 粉 ";break;case 4: cout<<" 綠 ";break;case 5: cout<<" 橙 ";break;case 6: cout<<" 白 ";break;} }cout<<endl; }//試色函數(shù) void trycolor(int s,Graph G)//s為著色的起點，本算法從0開始 {int i;if(s>G.vnum)//遞歸出口{output(G);system("pause");exit(1);}else{for(i=0;i<N;i++)//對每種色彩逐個測試{color[s]=i;if(colorsame(s,G)==0)//通過colorsame函數(shù)測試是否符合顏色要求trycolor(s+1,G);// 進(jìn)行下一塊著色}} }void main()//主函數(shù) {cout<<" ....美國地圖著色Loading.... "<<endl;cout<<"請問使用幾種顏色為地圖著色（7，6，5，4）？"<<endl;cin>>N;cout<<"供您選擇的顏色有："<<endl;inforc(); //輸出顏色信息Graph G;CreateGraph(G);PrintGraph(G);cout<<"美國地圖著色方案:\n";trycolor(0,G);//著色}

? ? ? ? 數(shù)組color[n]存儲n個頂點的著色方案，可以選擇的顏色為0到6。

? ? ? ? 當(dāng)s=0時，對當(dāng)前第0個頂點開始著色：若s>vnum，則已求得一個解，輸出著色方案即可。否則，依次對頂點s著色1-m，?若t與所有其它相鄰頂點無顏色沖突，則繼續(xù)為下一頂點著色；否則，回溯法，測試下一顏色。

總結(jié)

以上是生活随笔為你收集整理的[C++]美国地图着色问题C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。