已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。
public class Map {
private static final int BOARD_NUMBER = 31;
private String[] board = new String[BOARD_NUMBER];
private int[][] edge = new int[BOARD_NUMBER][BOARD_NUMBER];
//初始化所有顶点均涂色0
private int[] color = new int[BOARD_NUMBER];
public Map(String[] board, int[][] edge) {
this.board = board;
this.edge = edge;
}
public boolean colour(int colorKind) {
int vertex = 0; //从图中的一个顶点开始
//vertex从0~BOARD_NUMBER-1表示所有顶点
while(vertex < BOARD_NUMBER) {
int flag = 1;
//如果发现colorKind种颜色不能满足，返回false
if(vertex == -1) {
return false;
}
color[vertex]++;
//当涂色超过colorKind种，回溯
if(color[vertex] > colorKind) {
color[vertex] = 0;
vertex--;
continue;
}
for(int i = 0; i < vertex; ++i) {
//发现邻接点涂相同颜色
if (edge[vertex][i] == 1 && color[vertex] == color[i]) {
flag = 0;
break;
}
}
//发现邻接点涂相同颜色,该结点重涂
if(flag == 0) continue;
vertex++;
}
for(int i = 0; i < BOARD_NUMBER; ++i) {
System.out.println(board[i] + "涂色为：" + color[i]);
}
return true;
}
public static void main(String[] args) {
String board[]={"广西","广东","云南","贵州","湖南","江西","福建","浙江","安徽","湖北","重庆","四川","西藏","青海",
"新疆","甘肃","陕西","宁夏","内蒙","北京","黑龙江","吉林","辽宁","天津","河北","山西","河南","江苏","山东","上海","海南","台湾","香港","澳门"};
// 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、海南;
// 用邻接矩阵建立图结构
int edge[][]={
{0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//1
{1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//2
{1,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//3
{1,0,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//4
{1,1,0,1,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//5
{0,1,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//6
{0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//7
{0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0},//8
{0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0},//9
{0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0},//10
{0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//11
{0,0,1,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//12
{0,0,1,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//13
{0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//14
{0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//15
{0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0},//16
{0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0},//17
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0},//18
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0,0,0,0},//19
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0},//20
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0},//21
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0},//22
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0},//23
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0},//24
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,0,1,0,0},//25
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0},//26
{0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,1,0,0},//27
{0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0},//28
{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,0},//29
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},//30
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}//31
};
Map p = new Map(board, edge);
int colorKind = 1;
while(!p.colour(colorKind)) {
colorKind++;
}
System.out.println("最少要涂" + colorKind + "种颜色");
}
}
输出
广西涂色为：1 广东涂色为：2 云南涂色为：2 贵州涂色为：3 湖南涂色为：4 江西涂色为：1 福建涂色为：3 浙江涂色为：2 安徽涂色为：3 湖北涂色为：2 重庆涂色为：1 四川涂色为：4 西藏涂色为：1 青海涂色为：2 新疆涂色为：3 甘肃涂色为：1 陕西涂色为：3 宁夏涂色为：2 内蒙涂色为：4 北京涂色为：1 黑龙江涂色为：1 吉林涂色为：2 辽宁涂色为：1 天津涂色为：2 河北涂色为：3 山西涂色为：1 河南涂色为：4 江苏涂色为：1 山东涂色为：2 上海涂色为：3 海南涂色为：1 最少要涂4种颜色
