|
地图着色，需要每一个区域都使用一种颜色来进行填充，然后为了与相邻接壤的区域分开，就要求两个接壤的区域需要使用不同的颜色。四色定理的意思是，最多只需要四种颜色，就可以为所有的地图进行全部区域着色，且任意两个接壤的区域都是不同的颜色。在四色定理的指导下，我用Java来实现求解任意一副地图的所有可行的区域着色方案的算法，并求解下面这幅示例地图的所有着色方案：  算法思路：
将所有的区域进行编号，从0开始，然后用一个长度为区域总数的数组记录，称为颜色方案数组颜色方案数组的下标是区域编号，值是使用的颜色，代号为1、2、3、4四种颜色。初始化全部是0，也就是颜色0代表未着色，如果大于0，代表已着色，值就是颜色创建无权无向图，所有区域映射图的顶点，如果两个区域是接壤的，则对应图的两个顶点之间就是连通的，然后求出该无权无向图的记录有地图区域接壤关系的邻接矩阵0区域默认使用1号颜色，然后找到下一个区域，根据接壤关系的邻接矩阵和颜色方案数组，找到下一个区域的所有接壤区域已经使用过的颜色集，再反向求出可使用的颜色集如果下一个区域的可使用颜色集为空集，则当前递归分支结束。如果不为空集，则遍历所有可用颜色，然后递归调用，一个可用颜色为一个递归分支，着色下一个区域……递归方法在着色后进行判断，如果刚刚着了色的区域已经是最后一个区域了，则表示程序已经找到了地图着色方案。然后程序输出颜色方案数组，以展示可行的地图着色方案
第一步：将所有的区域进行编号，从0开始  第二步：创建无权无向图，所有区域映射图的顶点，如果两个区域是接壤的，则连通对应图的两个顶点  3、根据上面记录有地图区域接壤关系的无权无向图，求出该图的邻接矩阵。该邻接矩阵也是算法输入的数据来源  下面是我用Java实现的求解上面示例图的着色方案的算法。该算法的思想和精髓已经在下面的代码和其间的详尽注释中：
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* @author LiYang
* @ClassName FourColorTheorem
* @Description 四色定理探索实践类
* @date 2019/12/7 22:32
*/
public class FourColorTheorem {
//根据四色定理，最多只使用四种颜色，就可以为任何地图
//着色，并且保证相邻接壤的区域必须用不同的颜色
//---------------------------------------------
//注意，如果你的地图足够特别，也是有可能三种，甚至更少
//的颜色种类就完成着色，此时可以将下面的数字改小，然后
//查看控制台是否有结果输出，有结果输出则表示可行
private static final int MIN_NECESSARY_MAP_COLOR = 4;
/**
* 返回示例地图接壤信息的邻接矩阵
* @return 示例地图接壤信息的邻接矩阵
*/
public static int[][] initMapMatrix() {
//直接返回记录示例地图接壤信息的邻接矩阵
//要运行自己的地图，可以修改此邻接矩阵
return new int[][] {
{0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0},
{0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0}
};
}
/**
* 深拷贝数组
* @param source 数组拷贝源
* @return 数组副本
*/
public static int[] copyArray(int[] source) {
//创建新的数组
int[] copy = new int[source.length];
//拷贝赋值新数组
System.arraycopy(source, 0, copy, 0, source.length);
//返回深拷贝的副本
return copy;
}
/**
* 地图区域着色算法的递归执行方法
* @param nextArea 着色区域
* @param color 着色使用的颜色
* @param colorPlan 着色计划记录数组
* @param matrix 区域接壤的邻接矩阵
*/
public static void coloringMap(int nextArea, int color, int[] colorPlan, int[][] matrix) {
//将当前区域着色
colorPlan[nextArea] = color;
//如果已经全部着色，则打印结果
if (nextArea == colorPlan.length - 1) {
//打印当前递归分支的着色方案
System.out.println("找到着色方案：" + Arrays.toString(colorPlan));
//结束当前递归分支
return;
}
//当前区域更新为下一个区域
//准备为下一个区域进行着色
nextArea ++;
//下一个区域的可用颜色集
Set availableColor = new HashSet();
//初始化可用颜色集
for (int i = 1; i 0) {
//将接壤的已用颜色剔除
availableColor.remove(colorPlan[i]);
}
}
//遍历下一个区域的所有可用颜色
for (int available : availableColor) {
//分别递归调用本算法，尝试下一个区域着所有可用颜色集
coloringMap(nextArea, available, copyArray(colorPlan), matrix);
}
}
/**
* 地图区域着色算法的驱动方法
* @param matrix 地图接壤的邻接矩阵
*/
public static void coloringMap(int[][] matrix) {
//我们从0号区域开始，从哪个区域开始都一样
int nextArea = 0;
//颜色代号是1-4，本质是等价可互换的，用1开始就行
int color = 1;
//初始化着色方案
int[] colorPlan = new int[matrix.length];
//调用地图区域着色算法的递归执行方法
coloringMap(nextArea, color, colorPlan, matrix);
}
/**
* 运用四色定理，运行示例地图着色的算法
* @param args
*/
public static void main(String[] args) {
//获得记录示例地图接壤关系的邻接矩阵
int[][] matrix = initMapMatrix();
//运行示例地图着色的算法，并从控制台
//查看打印的着色方案
coloringMap(matrix);
}
}
运行FourColorTheorem类的main方法，控制台输出了很多可行的示例图着色方案！下面是我随意摘选的一部分示例图着色方案：
找到着色方案：[1, 2, 2, 3, 1, 1, 2, 3, 4, 2, 3]
找到着色方案：[1, 3, 2, 4, 2, 1, 3, 4, 2, 3, 4]
找到着色方案：[1, 4, 2, 4, 2, 1, 4, 3, 2, 1, 4]
找到着色方案：[1, 4, 4, 3, 3, 2, 4, 1, 3, 2, 1]
接下来我们验证算法求出的示例图着色方案。1号我们用红色，2号用黄色，3号用蓝色，4号用粉色，验证上面我随意筛选的四种示例图着色方案，地图着色后表明，该算法测试通过： 
|