中财网物业客服部的职能:算法设计与分析 5.8 图的 m 着色问题
来源：百度文库 编辑：中财网 时间：2024/04/29 08:58:04
* 5.8 图的 m 着色问题
*
* 给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 和各顶点着色，每
* 个顶点着一种颜色。是否有一种着色法使得图 G 中每条边的两个顶点着不同的颜
* 色。这个问题是图的 m 可着色判定问题。若一个图最少需要 m 种颜色才能使图
* 中的每条边连接的两个顶点着不同的颜色，则称这个数 m 为该图的色数。求一个
* 图的色数 m 的问题称为图的 m 可着色优化问题。
*
* 子集树，O(n*(m^n))时间复杂度
************************************************************/
import java.util.Arrays;
public class Coloring {
static int n; //图的顶点数
static int m; //可用颜色数
static boolean[][] a; //图的邻接矩阵
static int[] x; //当前解
static long sum; //当前找到的可 m 着色的方案数
/**
*
* @param matrix 地图
* @param mm 颜色数
* @return 着色方案数
*/
public static long mColoring(boolean[][] matrix, int mm) {
a = matrix;
n = a.length;
m = mm;
x = new int[n];
sum = 0;
trackback(0);
return sum;
}
private static void trackback(int t) {
if (t == n) {
sum++;
System.out.println(Arrays.toString(x));
} else {
for (int i = 0; i < m; i++) {
x[t] = i;
if (valid(t)) {
trackback(t + 1);
}
}
}
}
private static boolean valid(int t) {
//检查颜色可用性
for (int i = 0; i < n; i++) {
if (a[t][i] && x[i] == x[t]) {
return false;
}
}
return true;
}
}