数据结构-图的着色问题

问题描述：

        图的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);
    }
}