fac5_7.java

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

//本程序取自王晓东编著“算法分析与设计”第 171 页，例
//最大团问题的回溯解法
//
   class MaxClique 
   { 
    
     static int[]  x;          // 当前解
     static int n;             // 图Ｇ的顶点数
     static int cn ;           // 当前顶点数 
     static int bestn;         // 当前最大顶点数
     static int[] bestx;       // 当前最优解
     static boolean [][] a;      // 图Ｇ的邻接矩阵
    
    
     public static int maxClique(int[] v)  
      {
        x=new int[n+1];
        cn=0;
        bestn=0;
        bestx=v;
        backtrack(1);
        return bestn;
      }
     public static void backtrack(int i)
    {
      if(i>n)
       {//到达叶结点
       for(int j=1;j<=n;j++)
         bestx[j]=x[j];
       bestn=cn;
       return;
       }
      boolean ok=true;
      for(int j=1;j<i;j++)
        if(x[j]==1 && !a[i][j])
         {//i与j不相连
          ok=false;
          break;
         }
       if(ok)
         {//进入左子树
          x[i]=1;
          cn++;
          backtrack(i+1);
          cn--;
         }
       if(cn+n-i>bestn)
         {//进入右子树
          x[i]=0;
          backtrack(i+1);
         }
      }
    }
  
  
      public class Fac5_7{
      public static void main(String args[])
  {
     MaxClique abc=new MaxClique();
     int n1=5; 
     int ak[]=new int[n1+1];
     boolean [][] aw=new boolean[n1+1][n1+1];
      aw[1][1]=false;aw[1][2]=true; aw[1][3]=false; aw[1][4]=true; aw[1][5]=true;
      aw[2][1]=true; aw[2][2]=false;aw[2][3]=true;  aw[2][4]=false;aw[2][5]=true;
      aw[3][1]=false;aw[3][2]=true; aw[3][3]=false; aw[3][4]=false;aw[3][5]=true;
      aw[4][1]=true; aw[4][2]=false;aw[4][3]=false; aw[4][4]=false;aw[4][5]=true;
      aw[5][1]=true; aw[5][2]=true; aw[5][3]=true;  aw[5][4]=true; aw[5][5]=false; 
     abc.a=aw; 
     abc.n=n1;    
     System.out.println("最大团顶点数为 " + abc.maxClique(ak));
     for(int i=1;i<=n1;i++)
     System.out.print("  "+abc.bestx[i]);
     System.out.println();
  }
}