数据结构-图的着色问题
图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?
个人感觉图的着色问题类似与八皇后问题，使用回溯算法（试探法）解决
state[n]存储n个顶点的着色方案，可以选择的颜色为1到m。
当t=1时，对当前第t个顶点开始着色：若t>n，则已求得一个解，输出着色方案即可。否则，依次对顶点t着色1-m， 若t与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；否则，回溯，测试下一颜色。
package graph;
public class Graph2 {
static int[][] e ;//图的邻接矩阵表示
static int[] state ; //储存n个顶点的着色
static int color = 6;//共有几种颜色
static int count=0;
static void sear(int index) {
if (isOk(index)) {//判断当前状态能否着色
if (index == e.length - 1) {//若全部着色输出
count++;
} else {
for (int i = 1; i <= color; i++) {//遍历所有的颜色
state[index + 1] = i;
sear(index + 1);
}
}
}
}
private static void show(int index) {
for (int i = 1; i <= index; i++) {
System.out.print(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])//当两个节点是连同并且颜色一样则返回false
return false;
}
return true;
}
public static void main(String[] args) {
e=new int[][] {{0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1,0,1,1,0},//1
{0,0,0,0,1,0,0,0,1,1,0,1,1,0},//2
{0,0,0,0,1,0,0,0,0,1,0,0,0,1},//3
{0,0,1,1,0,1,0,0,0,0,1,1,0,0},//4
{0,0,0,0,1,0,1,0,0,0,0,0,1,1},
{0,0,0,0,0,1,0,1,0,0,1,0,0,0},
{0,0,0,0,0,0,1,0,1,0,1,1,1,0},//7
{0,1,1,0,0,0,0,1,0,1,0,0,1,0},
{0,1,1,1,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,0,1,1,0,0,0,0,0,1},
{0,1,1,0,1,0,0,1,0,0,0,0,0,1},
{0,1,1,0,0,1,0,1,1,0,0,0,0,0},
{0,0,0,1,0,1,0,0,0,0,1,1,0,0}};;
state=new int[e.length];
long l=System.currentTimeMillis();
sear(0);
long l2=System.currentTimeMillis();
System.out.println(count);
System.out.println(l2-l);
}
}package graph;
import java.util.Stack;
public class Graph {
static int[][] e ;//图的邻接矩阵表示
static int[] state ; //储存n个顶点的着色
static int color = 6;//共有几种颜色
static int count=0;
public static int setColor() {
Stack<Integer> s=new Stack<Integer>();//用于保存之前的着色颜色
int tindex=1;//当前节点
int tc=1;//当前颜色
state[tindex]=tc;
while(!s.isEmpty()||tc<=color) {
if(tindex>=e.length) {
tc=s.pop()+1;
tindex--;
state[tindex]=0;
}
if(tc>color) {
tc=s.pop()+1;
tindex--;
state[tindex]=0;
continue;
}
if(isOk(tindex,tc)) {//能着色
s.push(tc);
tindex++;
tc=1;
if(tindex==e.length) {
count++;
}
}else {//不能着色-遍历下一个颜色
tc++;
}
}
return 1;
}
private static boolean isOk(int index,int tc) {
state[index]=tc;
for (int i = 1; i < index; i++) {
if (e[index][i] == 1 && state[i] == state[index]) {//当两个节点是连同并且颜色一样则不满足返回false
state[index]=0;
return false;
}
}
return true;
}
private static void show(int index) {
for (int i = 1; i <= index; i++) {
System.out.print(state[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
e=new int[][] {{0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1,0,1,1,0},//1
{0,0,0,0,1,0,0,0,1,1,0,1,1,0},//2
{0,0,0,0,1,0,0,0,0,1,0,0,0,1},//3
{0,0,1,1,0,1,0,0,0,0,1,1,0,0},//4
{0,0,0,0,1,0,1,0,0,0,0,0,1,1},
{0,0,0,0,0,1,0,1,0,0,1,0,0,0},
{0,0,0,0,0,0,1,0,1,0,1,1,1,0},//7
{0,1,1,0,0,0,0,1,0,1,0,0,1,0},
{0,1,1,1,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,1,0,1,1,0,0,0,0,0,1},
{0,1,1,0,1,0,0,1,0,0,0,0,0,1},
{0,1,1,0,0,1,0,1,1,0,0,0,0,0},
{0,0,0,1,0,1,0,0,0,0,1,1,0,0}};;
state=new int[e.length];
long l=System.currentTimeMillis();
setColor();
long l2=System.currentTimeMillis();
System.out.println(count);
System.out.println(l2-l);
}
}