地图着色问题(java实现)
public class Coloring
{
private int colors;
private boolean [][]map;
private int []x;
private long sum; //解法种数
public Coloring(boolean map[][],int colors)
{
this.map=map;
this.colors=colors;
x=new int[map[0].length];
}
public long mColoring()
{
backtrack(1);
return sum;
}
private void backtrack(int t)
{
int n=map[0].length;
if(t>n)
{
sum++;
print(sum);
}
else
{
for(int i=1;i<=colors;i++)
{
x[t-1]=i;
if(ok(t)) backtrack(t+1);
}
}
}
private boolean ok(int k)
{
for(int j=0;j<k-1;j++)
{
if(map[k-1][j]&&(x[j]==x[k-1]))
return false;
}
return true;
}
private void print(long n)
{
System.out.println("第"+n+"种方案:");
for(int i=0;i<x.length;i++)
System.out.println("第"+(i+1)+"个结点的颜色是："+x[i]);
System.out.println();
}
public static void main(String []args)
{
boolean [][] map={{false,true,false,true},
{true,false,true,false},
{false,true,false,true},
{true,false,true,false} };
int colors=3;
Coloring mc=new Coloring(map,colors);
System.out.println("共找到了 "+mc.mColoring()+" 种方案！");
}
}