日撸代码300行：第35天（图的 m 着色问题）

日撸代码300行：第35天（图的 m 着色问题）

代码来自闵老师”日撸 Java 三百行（31-40天）“，链接：

**问题描述:**给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

	/*** ****************************************************************** Coloring.Output all possible schemes.* * @param paraNumColors   The number of colors.* ******************************************************************/public void coloring(int paraNumColors) {int tempNumNodes = Rows();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 = Rows();//System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = "//+ paraCurrentNumNodes + ", paraCurrentColoring" + String(paraCurrentColoring));// A complete scheme.if (paraCurrentNumNodes >= tempNumNodes) {System.out.println("Find one:" + String(paraCurrentColoring));return;  //自己写的时候少了return，数组越界了}//of iffor (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 (Data()[paraCurrentNumNodes -1][i] == 0) {continue; }//of ifif (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) {//It has the same color as the urn true;}//of if}//of for ireturn false;}//of colorConflictpublic 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);//loring(2);loring(3);}//of coloringTest/*** ***************************************************************** The entrance of program.* @param args   Not used now.* *****************************************************************/public static void main(String args[]) {//Graph tempGraph = new Graph(3);//System.out.println(tempGraph);//getConnectivityTest();//breadthFirstTraversalTest();//depthFirstTraversalTest();coloringTest();}//of main

思考两个问题：
（1）自己写程序的时候，少写了一个return，导致数组越界。
如果没有return，一直给节点着色，总会超过声明的数组长度（tempNumNodes）。paraCurrentColoring[paraCurrentNumNodes]= i;就越界了。
（2）为啥会输出所有的着色方案，感觉代码只是找到一个着色方案，循环在哪里？
仔细想了一下，循环就是for实现的。原本以为for是为了解决着色问题，为了填充不同的颜色。其实是为了控制起始节点的颜色，然后后面的节点会分别着与之前节点不同的颜色。这样就实现了循环输出不同的方案。这里也涉及到上面return的问题，return会回退到下一个方案。