回溯法求图的m着色问题

 

 

 

问题描述：给定无向图G和m种不同的颜色，用这些颜色为图G的各个点着色，每个顶点着一种颜色。是否有一种着色发使G中的每条边的两个顶点着不同种颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中的每一条边连接的两个顶点着不同种颜色，则称这个数m为该图的色数。图的色数m的问题称为图的m可着色优化问题。

 

 

 解题思路：有序地从顶点1着1号颜色开始，然后再试着顶点2的第几号颜色，如果顶点2也满足条件，那么继续着顶点3的颜色，如果此时顶点3没有可着的颜色，说明目前为止的尝试是无效的（不可能得到最终的解），那么此时应该回溯的上一顶点（即顶点2），将上一顶点着的颜色该着另一种符合要求的颜色..........如此尝试性地搜索加回溯，最后得到符合要求的解。

 

 

package 算法实验;
/**
 * 图的m着色类
 *回溯法求图的m着色问题
 */
public class mColoring {
	//定义变量和数组
	static int m,n;//m为颜色种数，n表示n个区域
	static int []x;//x[k]表示第k号区域的第x[k]号颜色
	static int [][]a;//用来存储图的邻接矩阵
    /**
     * 如何着色的方法
     */
     public void coloring(){
    	 x[1]=0;//每号区域从0号颜色开始
    	int k=1;//从1号区域开始
    	 while(k>0){
    	  x[k]=x[k]+1; 
    	  while((x[k]<=m)&&!(restrain(k)))//约束条件判断
    		  x[k]+=1;
    	  if(x[k]<=m)
    		  if(k==n){
    			  //输出各个区域着的颜色
    			  for(int i=1;i<=n;i++)
    			  System.out.println(+i+"号区域着"+x[i]+"号颜色；");
    			  System.out.println();
    		  }
    		  else {
    			  k++;
    			  x[k]=0;
    		  }
    	  else
    		  k--;//回溯
    	 }
     }
     /**
      * 约束条件的判断方法
      * @param k
      * @return
      */
     public boolean restrain(int k){
    	 for(int j=1;j<=k;j++)
    		 if((a[k][j]==1)&&(x[j]==x[k]))//相邻区域不能着同种颜色
    			 return false;
    	 return true;
     }
     /**
      * 程序入口，主函数
      * @param args
      */
   public static void main(String[] args){
	   m=4;n=5;//给m,n赋初始值
	   x = new int[n+1];//定义数组长度
	   //二维数组用来存储图的邻接矩阵
	   a=new int[][]{
				{0,0,0,0,0,0},//0表示两号区域之间不相邻
				{0,0,1,1,1,0},//1表示两号区域之间相邻
				{0,1,0,1,1,1},
				{0,1,1,0,1,0},
				{0,1,1,1,0,1},
				{0,0,1,0,1,0}
			};
	   mColoring mc = new mColoring();//实例化对象
	   System.out.println("各个点着的颜色是：");
	   mc.coloring();//调用着色方法
   }
     
}

 运行结果：

 

1号区域着4号颜色；
2号区域着3号颜色；
3号区域着1号颜色；
4号区域着2号颜色；
5号区域着1号颜色；

 

1号区域着4号颜色；
2号区域着3号颜色；
3号区域着1号颜色；
4号区域着2号颜色；
5号区域着4号颜色；

 

1号区域着4号颜色；
2号区域着3号颜色；
3号区域着2号颜色；
4号区域着1号颜色；
5号区域着2号颜色；

 

1号区域着4号颜色；
2号区域着3号颜色；
3号区域着2号颜色；
4号区域着1号颜色；
5号区域着4号颜色；