日撸java_day35

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

第 35 天: 图的 m 着色问题

 / * Coloring. Output all possible schemes. * * @param paraNumColors The number of colors. */ public void coloring(int paraNumColors) { // Step1. Initialize. int tempNumNodes = connectivityMatrix.gerRows(); 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) { // Step1. Initialize. int tempNumNodes = connectivityMatrix.gerRows(); System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = " + paraCurrentNumNodes + ", paraCurrentColoring" + Arrays.toString(paraCurrentColoring)); // A completed 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 directed 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(3); }// Of coloringTest

回溯法思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。