原文：
https://blog.csdn.net/qq_28888837/article/details/53284828
問題：圖的m-著色判定問題
給定無向連通圖G和m種不同的顏色翁锡。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色夕土，是否有一種著色法使G中任意相鄰的2個(gè)頂點(diǎn)著不同顏色?
4個(gè)頂點(diǎn)的無向圖
import java.util.Scanner;
public class Main {
static int[][] e = new int[5][5]; //存儲各個(gè)邊的情況連同為1 不連為0
static int[] state = new int[e.length]; //表示當(dāng)前染色情況
static int Colornum = 3;//共有幾種顏色
static void sear(int index) {//遞歸函數(shù)
if (isOk(index)) {//判斷當(dāng)前狀態(tài)能否滿足條件
if (index == e.length - 1) {//若已經(jīng)染到最后一個(gè)節(jié)點(diǎn)則輸出情況
Show(index);
} else {
for (int i = 1; i <= Colornum; i++) {//將所有 的顏色情況給遍歷
state[index + 1] = i;//假如下一個(gè)染色馆衔，
sear(index + 1);//進(jìn)入下次遞歸并且在遞歸的入口判斷是否滿足條件
}
}
}
}
//打印當(dāng)前狀態(tài)
private static void Show(int index) {
for (int i = 1; i <= index; i++) {
System.out.println(i + "is " + "Color " + state[i]);
}
System.out.println();
}
//判斷是否能染色
private static boolean isOk(int index) {
for (int i = 1; i < index; i++) {
if (e[index][i] == 1 && state[i] == state[index])//當(dāng)兩個(gè)節(jié)點(diǎn)是連同并且顏色一樣則不滿足返回false
return false;
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
//輸入邊的情況
for (int i = 1; i <= n; i++) {
int a = in.nextInt();
int b = in.nextInt();
e[a][b] = 1;
e[b][a] = 1;
}
//從0開始遞歸，但0不是一個(gè)節(jié)點(diǎn)
sear(0);
}
}
