中国+美国可选择地图着色问题
地图着色问题
地图着色问题（Graph Coloring Problem, GCP） 又称着色问题，是最著名的NP-完全问题之一。
- 图的m可着色判定问题
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。
- 图的m可着色优化问题
若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。
解决方法
回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
队列
队列（queue）是一种特殊的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
代码展示
美国地图着色 代码（c++）
#include<iostream>
#include<iomanip>
#include <string>
#include <queue>
using namespace std;
int N;//选择颜色个数
//用队列来储存所有的颜色,当选择了颜色的数量，就在队列里生成所选数量的颜色，每次选择优先选择队首颜色，用后放回队尾，以此实现4种以上颜色的使用。
queue<int> q;
int color[50]= {0}; //存储对应块对应颜色
typedef struct { //定义图
string state[50]; //各州或省的名称
int a[50][50]; //州或省的邻接矩阵
int vnum,arcnum;//图的顶点数和边数
} Graph;
//输出颜色信息
void inforc() {
cout<<"1.红色 2.蓝色 3.黄色 4.粉色 ";
if(N>=5) cout<<"5.绿色 ";
if(N>=6) cout<<"6.橙色 ";
if(N>=7) cout<<"7.白色 ";
cout<<endl<<endl;
}
//输入地图的信息
void CreateAmericanGraph(Graph &G) {
G.vnum=50;
G.arcnum=212;
//初始化矩阵
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] = "爱达荷州";G.state[4] = "内华达州";
G.state[5] = "蒙他拿州";G.state[6] = "犹他州";G.state[7] = "亚利桑那州";G.state[8] = "怀俄明州";G.state[9] = "科罗拉多州";
G.state[10] = "新墨西哥州";G.state[11] = "北达科他州";G.state[12] = "南达科他州";G.state[13] = "内布拉斯加州";G.state[14] = "堪萨斯州";
G.state[15] = "俄克拉荷马州";G.state[16] = "德克萨斯州";G.state[17] = "明尼苏达州";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] = "佛罗里达州";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<<"省或州的信息：\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++){
//如果邻接矩阵的值为1，说明对应两个州接壤
if(G.a[i][j]==1){
cout<<G.state[i]<<"与"<<G.state[j]<<"接壤 ";
}
}
cout<<endl<<endl;
}
cout<<endl;
}
//颜色比对函数
int colorsame(int s,Graph G) {
int i,flag=0; //初始化标志位为零
for(i=0; i<s; i++){ //与已经涂过色的州进行比对
if(G.a[i][s]==1&&color[i]==color[s]) { //两州接壤且颜色相同
flag=1; //标志为一，在trycolor函数中更换颜色
break;
}
}
return flag; //返回标志值
}
//输出函数
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]<<":";//相应州名
switch(color[i]) { //将数字转换成相应颜色
case 0:
cout<<" 红 ";
break;
case 1:
cout<<" 蓝 ";
break;
case 2:
cout<<" 黄 ";
break;
case 3:
cout<<" 粉 ";
break;
case 4:
cout<<" 绿 ";
break;
case 5:
cout<<" 橙 ";
break;
case 6:
cout<<" 白 ";
break;
}
}
cout<<endl;
}
//通过给定颜色数量初始化颜色队列
void initColor(int n){
for(int i=0;i<n;i++){
q.push(i);
}
}
//上色函数
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++) { //对每种色彩逐个测试
int tmp = q.front();
q.pop();
color[s]=tmp;//把该序号的州或省上色
q.push(tmp);
if(colorsame(s,G)==0){//通过colorsame函数测试是否符合颜色要求，如果不符合就选择下一种颜色
trycolor(s+1,G);// 进行下一块着色
}
}
}
}
void operate(Graph G){
PrintGraph(G);
while(1){
cout<<"请问使用几种颜色为地图着色（7，6，5，4）？";
cin>>N;
if(N<4||N>7){
cout << "Error Data！" << endl;
}else{
cout<<"供您选择的颜色有：";
inforc(); //输出颜色信息
break;
}
}
initColor(N);
trycolor(0,G);
}
int main() {
int n,n1;
Graph G;
while(1) {
cout << " " << endl;
cout << "--------------------------------------" << endl;
cout << "| 地图着色问题 |" << endl;
cout << "| |" << endl;
cout << "| 1.选择地图 |" << endl;
cout << "| |" << endl;
cout << "| 0.退出 |" << endl;
cout << "| |" << endl;
cout << "--------------------------------------" << endl;
cout << " 请选择:";
cin >> n;
cout << endl;
if(n==0) break;
if(n<4&&n>0) {
cout << " " << endl;
cout << "--------------------------------------" << endl;
cout << "| 选择地图 |" << endl;
cout << "| |" << endl;
cout << "| 1.美国地图 |" << endl;
cout << "| |" << endl;
cout << "| 0.退出 |" << endl;
cout << "| |" << endl;
cout << "--------------------------------------" << endl;
cout << " 请选择:";
cin >> n1;
if(n1==0){
break;
} else if(n1==1) {
CreateAmericanGraph(G);
operate(G);
} else {
cout << "Error Data!" << endl;
}
} else {
cout << "Error Data!" << endl;
}
}
return 0;
}
结果
中国+美国地图着色 代码（c++）
#include<iostream>
#include<iomanip>
#include <string>
#include <queue>
using namespace std;
int N;//选择颜色个数
//用队列来储存所有的颜色,当选择了颜色的数量，就在队列里生成所选数量的颜色，每次选择优先选择队首颜色，用后放回队尾，以此实现4种以上颜色的使用。
queue<int> q;
int color[50]= {0}; //存储对应块对应颜色
typedef struct { //定义图
string state[50]; //各州或省的名称
int a[50][50]; //州或省的邻接矩阵
int vnum,arcnum;//图的顶点数和边数
} Graph;
//输出颜色信息
void inforc() {
cout<<"1.红色 2.蓝色 3.黄色 4.粉色 ";
if(N>=5) cout<<"5.绿色 ";
if(N>=6) cout<<"6.橙色 ";
if(N>=7) cout<<"7.白色 ";
cout<<endl<<endl;
}
//输入地图的信息
void CreateAmericanGraph(Graph &G) {
G.vnum=50;
G.arcnum=212;
//初始化矩阵
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] = "爱达荷州";G.state[4] = "内华达州";
G.state[5] = "蒙他拿州";G.state[6] = "犹他州";G.state[7] = "亚利桑那州";G.state[8] = "怀俄明州";G.state[9] = "科罗拉多州";
G.state[10] = "新墨西哥州";G.state[11] = "北达科他州";G.state[12] = "南达科他州";G.state[13] = "内布拉斯加州";G.state[14] = "堪萨斯州";
G.state[15] = "俄克拉荷马州";G.state[16] = "德克萨斯州";G.state[17] = "明尼苏达州";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] = "佛罗里达州";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 CreateChinaGraph(Graph &G) {
G.vnum=34;
G.arcnum=140;
//初始化矩阵
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]="贵州";G.state[4]="湖南";
G.state[5]="江西";G.state[6]="福建";G.state[7]="浙江";G.state[8]="安徽";G.state[9]="湖北";
G.state[10]="重庆";G.state[11]="四川";G.state[12]="西藏";G.state[13]="青海";G.state[14]="新疆";
G.state[15]="甘肃";G.state[16]="陕西";G.state[17]="宁夏";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]="香港";G.state[33]="澳门";
G.a[0][1]=1;G.a[0][2]=1;G.a[0][3]=1;G.a[0][4]=1;
G.a[1][0]=1;G.a[1][4]=1;G.a[1][5]=1;G.a[1][6]=1;G.a[1][32]=1;G.a[1][33]=1;
G.a[2][0]=1;G.a[2][3]=1;G.a[2][11]=1;G.a[2][12]=1;
G.a[3][0]=1;G.a[3][2]=1;G.a[3][4]=1;G.a[3][10]=1;G.a[3][11]=1;
G.a[4][0]=1;G.a[4][1]=1;G.a[4][3]=1;G.a[4][5]=1;G.a[4][9]=1;G.a[4][10]=1;
G.a[5][1]=1;G.a[5][4]=1;G.a[5][6]=1;G.a[5][7]=1;G.a[5][8]=1;G.a[5][9]=1;
G.a[6][1]=1;G.a[6][5]=1;G.a[6][7]=1;
G.a[7][5]=1;G.a[7][6]=1;G.a[7][8]=1;G.a[7][27]=1;G.a[7][29]=1;
G.a[8][5]=1;G.a[8][7]=1;G.a[8][9]=1;G.a[8][26]=1;G.a[8][27]=1;G.a[8][28]=1;
G.a[9][4]=1;G.a[9][5]=1;G.a[9][8]=1;G.a[9][10]=1;G.a[9][16]=1;G.a[9][26]=1;
G.a[10][3]=1;G.a[10][4]=1;G.a[10][9]=1;G.a[10][11]=1;G.a[10][16]=1;
G.a[11][2]=1;G.a[11][3]=1;G.a[11][10]=1;G.a[11][12]=1;G.a[11][13]=1;G.a[11][15]=1;G.a[11][16]=1;
G.a[12][2]=1;G.a[12][11]=1;G.a[12][13]=1;G.a[12][14]=1;
G.a[13][11]=1;G.a[13][12]=1;G.a[13][14]=1;G.a[13][15]=1;
G.a[14][12]=1;G.a[14][13]=1;G.a[14][15]=1;
G.a[15][11]=1;G.a[15][13]=1;G.a[15][14]=1;G.a[15][16]=1;G.a[15][17]=1;G.a[15][18]=1;
G.a[16][9]=1;G.a[16][10]=1;G.a[16][11]=1;G.a[16][15]=1;G.a[16][17]=1;G.a[16][18]=1;G.a[16][25]=1;G.a[16][26]=1;
G.a[17][15]=1;G.a[17][16]=1;G.a[17][18]=1;
G.a[18][15]=1;G.a[18][16]=1;G.a[18][17]=1;G.a[18][20]=1;G.a[18][21]=1;G.a[18][22]=1;G.a[18][24]=1;G.a[18][25]=1;
G.a[19][23]=1;G.a[19][24]=1;
G.a[20][18]=1;G.a[20][21]=1;
G.a[21][18]=1;G.a[21][20]=1;G.a[21][22]=1;
G.a[22][18]=1;G.a[22][21]=1;G.a[22][24]=1;
G.a[23][19]=1;G.a[23][24]=1;
G.a[24][18]=1;G.a[24][19]=1;G.a[24][22]=1;G.a[24][23]=1;G.a[24][25]=1;G.a[24][26]=1;G.a[24][28]=1;
G.a[25][16]=1;G.a[25][18]=1;G.a[25][24]=1;G.a[25][26]=1;
G.a[26][8]=1;G.a[26][9]=1;G.a[26][16]=1;G.a[26][24]=1;G.a[26][25]=1;G.a[26][28]=1;
G.a[27][7]=1;G.a[27][8]=1;G.a[27][28]=1;G.a[27][29]=1;
G.a[28][8]=1;G.a[28][24]=1;G.a[28][26]=1;G.a[28][27]=1;
G.a[29][7]=1;G.a[29][27]=1;
G.a[32][1]=1;
G.a[33][1]=1;
}
//输出地图的信息
void PrintGraph(Graph G) {
int i,j;
cout<<"省或州的信息：\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++){
//如果邻接矩阵的值为1，说明对应两个州接壤
if(G.a[i][j]==1){
cout<<G.state[i]<<"与"<<G.state[j]<<"接壤 ";
}
}
cout<<endl<<endl;
}
cout<<endl;
}
//颜色比对函数
int colorsame(int s,Graph G) {
int i,flag=0; //初始化标志位为零
for(i=0; i<s; i++){ //与已经涂过色的州进行比对
if(G.a[i][s]==1&&color[i]==color[s]) { //两州接壤且颜色相同
flag=1; //标志为一，在trycolor函数中更换颜色
break;
}
}
return flag; //返回标志值
}
//输出函数
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]<<":";//相应州名
switch(color[i]) { //将数字转换成相应颜色
case 0:
cout<<" 红 ";
break;
case 1:
cout<<" 蓝 ";
break;
case 2:
cout<<" 黄 ";
break;
case 3:
cout<<" 粉 ";
break;
case 4:
cout<<" 绿 ";
break;
case 5:
cout<<" 橙 ";
break;
case 6:
cout<<" 白 ";
break;
}
}
cout<<endl;
}
//通过给定颜色数量初始化颜色队列
void initColor(int n){
for(int i=0;i<n;i++){
q.push(i);
}
}
//上色函数
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++) { //对每种色彩逐个测试
int tmp = q.front();
q.pop();
color[s]=tmp;//把该序号的州或省上色
q.push(tmp);
if(colorsame(s,G)==0){//通过colorsame函数测试是否符合颜色要求，如果不符合就选择下一种颜色
trycolor(s+1,G);// 进行下一块着色
}
}
}
}
void operate(Graph G){
PrintGraph(G);
while(1){
cout<<"请问使用几种颜色为地图着色（7，6，5，4）？";
cin>>N;
if(N<4||N>7){
cout << "Error Data！" << endl;
}else{
cout<<"供您选择的颜色有：";
inforc(); //输出颜色信息
break;
}
}
initColor(N);
trycolor(0,G);
}
int main() {
int n,n1;
Graph G;
while(1) {
cout << " " << endl;
cout << "--------------------------------------" << endl;
cout << "| 地图染色 |" << endl;
cout << "| |" << endl;
cout << "| 1.选择地图 |" << endl;
cout << "| |" << endl;
cout << "| 0.退出 |" << endl;
cout << "| |" << endl;
cout << "--------------------------------------" << endl;
cout << " 请选择:";
cin >> n;
cout << endl;
if(n==0) break;
if(n<4&&n>0) {
cout << " " << endl;
cout << "--------------------------------------" << endl;
cout << "| 选择地图 |" << endl;
cout << "| |" << endl;
cout << "| 1.中国地图 |" << endl;
cout << "| |" << endl;
cout << "| 2.美国地图 |" << endl;
cout << "| |" << endl;
cout << "| 0.退出 |" << endl;
cout << "| |" << endl;
cout << "--------------------------------------" << endl;
cout << " 请选择:";
cin >> n1;
if(n1==0){
break;
} else if(n1==1) {
CreateChinaGraph(G);
operate(G);
} else if(n1==2) {
CreateAmericanGraph(G);
operate(G);
} else {
cout << "Error Data!" << endl;
}
} else {
cout << "Error Data!" << endl;
}
}
return 0;
}
结果
