日撸Java三百行（day35：图的m着色问题）

大家好，欢迎来到IT知识分享网。

目录

一、问题描述

二、思路分析

三、代码实现

总结

一、问题描述

在高中学习排列组合的时候，有一个非常经典的问题，就是涂色问题，即用m种颜色给n块区域涂色，要求每块区域只能涂同一种颜色且相邻区域的颜色不能相同，问一共有多少种涂色方案。还记得当时自己是怎么做的吗？下面我们就用一个具体的例子来回顾一下。

如下图，共有A、B、C、D四块区域，用五种颜色给它们涂色，要求每块区域只能涂同一种颜色且相邻区域的颜色不能相同，请问一共有多少种涂色方案？

采用枚举法，第一步，给A区域涂色，由于A区域是第一个涂色的区域，没有任何颜色限制，所以有5种方法； 第二步，给B区域涂色，B区域与A区域相邻，使得B区域不能涂A区域涂过的颜色，所以共有4种方法；第三步，给C区域涂色，C区域与B区域相邻，使得C区域不能涂B区域涂过的颜色，所以共有4种方法；第四步，给D区域涂色，D区域与B、C区域都相邻，使得D区域不能涂B、C区域涂过的颜色，所以共有3种方法。最后，根据分步乘法计数原理，得到共有5*4*4*3=240种方案。

如果这只是高中的一道数学题，那必然不会放到这里来说，所以接下来我们就要将它抽象成图。显然，一块一块的区域可以看作图的一个个节点，因此给区域涂色就是给节点涂色，要求相邻区域的颜色不能相同就是要求邻接节点的颜色不能相同，所以上述例子就可以改写如下（区域与区域相邻显然是一个双向相邻，所以这里我们需要用到的是无向图）：

 这也就是今天我们要讨论的问题——图的m着色问题。

二、思路分析

那么该如何来解决这个问题呢？对于排列组合给区域涂色的问题，我们使用的是枚举法，同理，图的m着色问题我们同样可以使用枚举法（穷举法）来解决，也就是使用暴力解题法来完成。仍然以上图为例，进行具体说明：

• 将A、B、C、D四个节点编号为0、1、2、3号节点，将五种颜色编号为0、1、2、3、4号颜色，然后开始涂色。
• 假设从0号节点开始涂色0号颜色，那么1号节点可以涂1、2、3、4号颜色。
• 如果1号节点涂色1号颜色，那么2号节点可以涂色0、2、3、4号颜色；如果1号节点涂色2号颜色，那么2号节点可以涂色0、1、3、4号颜色；如果1号节点涂色3号颜色，那么2号节点可以涂色0、1、2、4号颜色；如果1号节点涂色4号颜色，那么2号节点可以涂色0、1、2、3号颜色。
• 如果1号节点涂色1号颜色，2号节点涂色0号颜色，那么3号节点可以涂色2、3、4号颜色；如果1号节点涂色1号颜色，2号节点涂色2号颜色，那么3号节点可以涂色0、3、4号颜色；如果1号节点涂色1号颜色，2号节点涂色3号颜色，那么3号节点可以涂色0、2、4号颜色……

以上就是这个问题的暴力解题法。

接下来，我们思考如何用代码来实现。如下图，仍然对节点和颜色分别进行从0开始的编号，并以节点总数为长度设置一个颜色标记数组，这样一来颜色标记数组的下标就与节点的编号达成了一致；颜色标记数组中的具体元素使用颜色编号来填充，这样通过数组下标就可以知道几号节点涂色了几号颜色；再设置一个默认初始值-1用于表示节点还未被涂色。

然后，我们从左往右（即从下标为0的节点开始）对颜色标记数组中的数据元素进行枚举，也就是用颜色编号进行填充，注意邻接节点在颜色标记数组中对应的位置不能存放相同的颜色编号。

我们暂时就分析到这里，剩下的内容在下面的代码实现过程中再继续。

三、代码实现

首先，进行初始化，如下：

 / * * Coloring. Output all possible schemes. * * @param paraNumColors The number of colors. * */ public void coloring(int paraNumColors) { // Step 1. Initialize. int tempNumNodes = connectivityMatrix.getRows(); int[] tempColorScheme = new int[tempNumNodes]; Arrays.fill(tempColorScheme, -1);

同样利用connectivityMatrix.getRows()获得节点总数tempNumNodes，然后将其作为数组长度创建一个int类型的颜色标记数组tempColorScheme，最后利用Array.fill()方法对tempColorScheme填充默认初始值-1。

补充：

Array.fill(数组名，默认初始值)方法：用于对一个数组快速填充同一默认初始值

然后，创建关键方法（其实也是对上面coloring方法的一个重载），如下：

 / * * Coloring. Output all possible schemes. * * @param paraNumColors The number of colors. * @param paraCurrentNumNodes The number of nodes that have been colored. * @param paraCurrentColoring The array recording the coloring scheme. * */ public void coloring(int paraNumColors, int paraCurrentNumNodes, int[] paraCurrentColoring) { // Step 1. Initialize. int tempNumNodes = connectivityMatrix.getRows(); System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = " + paraCurrentNumNodes + ", paraCurrentColoring" + Arrays.toString(paraCurrentColoring)); // A complete scheme. if (paraCurrentNumNodes >= tempNumNodes) { System.out.println("Find one:" + Arrays.toString(paraCurrentColoring)); return; } // Of if // Try all possible colors. for (int i = 0; i < paraNumColors; i++) { paraCurrentColoring[paraCurrentNumNodes] = i; if (!colorConflict(paraCurrentNumNodes + 1, paraCurrentColoring)) { coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring); } // Of if } // Of for i } // Of coloring

该方法输入了三个参数，其中paraNumColors表示一共有几种颜色，paraCurrentNumNodes表示当前涂色节点的编号（即当前涂色节点在颜色标记数组中的对应下标），paraCurrentColoring表示当前的颜色标记数组。然后，通过一条输出语句将此时三个参数的值进行输出。

在程序运行过程中，逐步向颜色标记数组输入颜色编号，当paraCurrentNumNodes >= tempNumNodes即当前涂色节点的编号 >= 节点总数时，说明所有的节点均已完成了一次涂色，也就是说找到了一种涂色方案，此时直接输出结果（即输出当前的颜色标记数组）。

当paraCurrentNumNodes没有大于等于tempNumNodes即当前涂色节点的编号没有大于等于节点总数时，则进入循环，对节点进行涂色。在for循环中paraCurrentColoring[paraCurrentNumNodes] = i 表示将 i 号颜色的编号 i 输入当前涂色节点在颜色标记数组中的对应位置，相当于给当前涂色节点涂上 i 号颜色；接着，借助一个if语句，使得当涂色不冲突时继续给编号加1的节点（相当于在颜色标记数组中向右移动一格）进行涂色，而当涂色冲突时则给当前涂色节点涂上 i + 1 号颜色后，再次进行涂色冲突判断。

创建一个判断涂色是否冲突的方法，如下：

 / * * Coloring conflict or not. Only compare the current last node with previous * ones. * * @param paraCurrentNumNodes The current number of nodes. * @param paraColoring The current coloring scheme. * @return Conflict or not. * */ public boolean colorConflict(int paraCurrentNumNodes, int[] paraColoring) { for (int i = 0; i < paraCurrentNumNodes - 1; i++) { // No direct connection. if (connectivityMatrix.getValue(paraCurrentNumNodes - 1, i) == 0) { continue; } // Of if if (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) { return true; } // Of if } // Of for i return false; } // Of colorConflict

connectivityMatrix.getValue()调用了之前整数矩阵类IntMatrix的getValue()方法，用于获得整数矩阵对象connectivityMatrix的某个具体元素值；然后利用了我们之前进行图的连通性检测的结论，即如果连通矩阵中某个元素的值为0，那么该元素行标对应的节点到该元素列标对应的节点不连通，不连通必然不邻接，也就不会发生涂色冲突，所以直接continue结束本次循环，返回false，代表涂色不冲突；但是如果paraColoring[paraCurrentNumNodes – 1] = paraColoring[ i ]，则说明涂色会发生冲突，于是返回true。

最后，设置一个单元测试，如下：

 / * * Coloring test. * */ public static void coloringTest() { int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 } }; Graph tempGraph = new Graph(tempMatrix); // tempGraph.coloring(2); tempGraph.coloring(3); } // Of coloringTest

完整的程序代码：

 / * * Coloring. Output all possible schemes. * * @param paraNumColors The number of colors. * */ public void coloring(int paraNumColors) { // Step 1. Initialize. int tempNumNodes = connectivityMatrix.getRows(); int[] tempColorScheme = new int[tempNumNodes]; Arrays.fill(tempColorScheme, -1); coloring(paraNumColors, 0, tempColorScheme); } // Of coloring / * * Coloring. Output all possible schemes. * * @param paraNumColors The number of colors. * @param paraCurrentNumNodes The number of nodes that have been colored. * @param paraCurrentColoring The array recording the coloring scheme. * */ public void coloring(int paraNumColors, int paraCurrentNumNodes, int[] paraCurrentColoring) { // Step 1. Initialize. int tempNumNodes = connectivityMatrix.getRows(); System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = " + paraCurrentNumNodes + ", paraCurrentColoring" + Arrays.toString(paraCurrentColoring)); // A complete scheme. if (paraCurrentNumNodes >= tempNumNodes) { System.out.println("Find one:" + Arrays.toString(paraCurrentColoring)); return; } // Of if // Try all possible colors. for (int i = 0; i < paraNumColors; i++) { paraCurrentColoring[paraCurrentNumNodes] = i; if (!colorConflict(paraCurrentNumNodes + 1, paraCurrentColoring)) { coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring); } // Of if } // Of for i } // Of coloring / * * Coloring conflict or not. Only compare the current last node with previous * ones. * * @param paraCurrentNumNodes The current number of nodes. * @param paraColoring The current coloring scheme. * @return Conflict or not. * */ public boolean colorConflict(int paraCurrentNumNodes, int[] paraColoring) { for (int i = 0; i < paraCurrentNumNodes - 1; i++) { // No direct connection. if (connectivityMatrix.getValue(paraCurrentNumNodes - 1, i) == 0) { continue; } // Of if if (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) { return true; } // Of if } // Of for i return false; } // Of colorConflict / * * Coloring test. * */ public static void coloringTest() { int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 } }; Graph tempGraph = new Graph(tempMatrix); // tempGraph.coloring(2); tempGraph.coloring(3); } // Of coloringTest / * * The entrance of the program. * * @param args Not used now. * */ public static void main(String args[]) { System.out.println("Hello!"); Graph tempGraph = new Graph(3); System.out.println(tempGraph); // Unit test. getConnectivityTest(); breadthFirstTraversalTest(); depthFirstTraversalTest(); coloringTest(); } // Of main

部分运行结果：

总结

对于图的m着色问题，我们使用的是枚举法，也是一种暴力解题法。对于人来说，枚举法似乎看起来是一种“笨方法”，因为它没有特别高的技术含量而且还很繁琐，但是对于计算机而言则不然，暴力解题法的逻辑相对简单直接，利用计算机比较容易实现，而且当规模不是很多的时候，暴力解题法可能比复杂的优化算法更为高效。总之，学习计算机万能的暴力解题法是必不可少的。