/*
* 图的m着色问题-回溯法-子集树
* time:2012-1-2
* 下标从1开始
* 测试数据:
* 这个无向图有8条边,5个顶点,采用5种颜色进行填充,一共会产生360中填充的方案
* public static int edge[][]={{0,0,0,0,0,0},
{0,0,1,1,1,0},
{0,1,0,1,1,1},
{0,1,1,0,1,0},
{0,1,1,1,0,1},
{0,0,1,0,1,0}};
*/
package com.book.java;
public class Project42_Coloring {
public static int m;//代表颜色的种类数量
public static int n;//代表顶点的个数
public static int edge[][]={{0,0,0,0,0,0},//存放图的连接矩阵其中,没有边
相互连接用0表示,顶点相同用0表示
{0,0,1,1,1,0},
{0,1,0,1,1,1},
{0,1,1,0,1,0},
{0,1,1,1,0,1},
{0,0,1,0,1,0}};
public static int x[];//记录着色的方案
public static int count;//记录着色方案的个数
public static void main(String[] args) {
m=5; //初始化颜色的总个数为5
n=edge.length-1; //初始化顶点的数量
count=0; //初始化着色的方案的个数0
x=new int[n+1]; //初始化记录着色的方案
traceback(1);
if(count==0)
{
System.out.println("没有适合的着色方案,颜色太少");
}
}
public static boolean place(int i,int num)//判断在 num这个顶点能否放置i
这种颜色
{
for(int k=1;k<num;k++)
{
if(edge[num][k]==1)//判断两个顶点之间是否连线
{
if(x[k]==i)//判断有连线的顶点的另一边是否与放置i这种颜色冲突
{
return false;
}
}
评论4