fac5_8.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 174 页，例
//图的m着色问题的回溯解法
//
 
    class Coloring
      {
        static int n;
        static int m;
        static boolean [][]a;
        static int []x;
        static long sum;
      public static long mColoring(int mm)
        {
          m=mm;
          sum=0;
          backtrack(1);
          return sum;
        }

      private static void backtrack(int t)
        {
          if(t>n)
            {
             sum++;
             for(int i=1;i<=n;i++)
               System.out.print(x[i]+"  ");
             System.out.println();
            }
          else
            for(int i=1;i<=m;i++)
             {
              x[t]=i;
              if(ok(t))backtrack(t+1);
              }
        }
       private static boolean ok(int k)
         {
           for(int j=1;j<=n;j++)
            if(a[k][j] && (x[j]==x[k]))return false;
           return true;
         }
   }//

   public class Fac5_8{
      public static void main(String args[])
  {
     Coloring abc=new Coloring();
     int n1=5;
     int m1=4;
     int x1[]=new int[n1+1];
     boolean a1[][]=new boolean [n1+1][n1+1];
      a1[1][1]=false;a1[1][2]=true; a1[1][3]=true; a1[1][4]=true; a1[1][5]=false;
      a1[2][1]=true; a1[2][2]=false;a1[2][3]=true; a1[2][4]=true; a1[2][5]=true;
      a1[3][1]=true; a1[3][2]=true; a1[3][3]=false;a1[3][4]=true; a1[3][5]=false;
      a1[4][1]=true; a1[4][2]=true; a1[4][3]=true; a1[4][4]=false;a1[4][5]=true;
      a1[5][1]=false;a1[5][2]=true; a1[5][3]=false;a1[5][4]=true; a1[5][5]=false;
      for(int k=0;k<=n1;k++)
        x1[k]=0;
     abc.x=x1;
     abc.a=a1;         
     abc.n=n1;
     abc.m=m1;      
     System.out.println("图的m着色问题的最大可解方案数为 " + abc.mColoring(m1));
  }
}