日撸代码300行：第35天（图的 m 着色问题）
/**
* *****************************************************************
* all possible schemes.
*
* @param paraNumColors The number of colors.
* *****************************************************************
*/
public void coloring(int paraNumColors) {
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();
//("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = "
//+ paraCurrentNumNodes + ", paraCurrentColoring" + (paraCurrentColoring));
// A complete scheme.
if (paraCurrentNumNodes >= tempNumNodes) {
System.out.println("Find one:" + Arrays.toString(paraCurrentColoring));
return; //自己写的时候少了return，数组越界了
}//of if
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.getData()[paraCurrentNumNodes -1][i] == 0) {
continue;
}//of if
if (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) {
//It has the same color as the previous nodes.
return true;
}//of if
}//of for i
return false;
}//of colorConflict
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);
//(2);
tempGraph.coloring(3);
}//of coloringTest
/**
* ****************************************************************
* The entrance of program.
* @param args Not used now.
* ****************************************************************
*/
public static void main(String args[]) {
//Graph tempGraph = new Graph(3);
//(tempGraph);
//getConnectivityTest();
//breadthFirstTraversalTest();
//depthFirstTraversalTest();
coloringTest();
}//of main