地图着色问题(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() " 种方案！");
}
}

上一篇： 软件工程学之软件过程（软件工程实践之二）
下一篇： 使用Hibernate Oracle9i R2 处理Clob大文本数据

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有