-
C++ 算法设计与分析 地图着色问题（中国+美国）
中国+美国可选择地图着色问题
地图着色问题
地图着色问题（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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
结果
中国+美国地图着色 代码（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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
结果
-
相关阅读:
java基础面试题：说说协程，进程和线程的区别和联系
CSS之垂直水平居中的背后
elasticsearch 7.x的 常用命令
PD充电驱动解析
汉字风格迁移---结合本地和全局特征学习的中文字体迁移
5_system_design_experience
Java- IO流
vue2和vue3响应式的理解及如何进行依赖收集
史上最全的neo4j图数据库教程：基于neo4j搭建金融风控图谱详细教程
Redis~02 缓存：更新数据时如何保证MySQL和Redis中的数据一致性？
- 原文地址：https://blog.csdn.net/weixin_55764157/article/details/125478350
