// 哈密尔顿回路问题
public class Hamilton {
 
 // 图中顶点个数为n，图的邻接矩阵为c[][]，存放回路的顶点序号x[]，在这里，n个顶点的标号是:0，1，2，...，n-1
 public void hamilton(int n,int x[],int c[][]){
  
      boolean[] s=new boolean[n]; // 记录n个顶点的使用与否
      // 初始化解向量x[]，使用向量s[]
      for(int i=0;i<n;i++){
           x[i]=-1;
           s[i]=false;
      }
  
      s[0]=true;
      x[0]=0;  // 从序号为0的顶点开始搜索
      int k=1; // 初始深度是1，因为有n个结点，且第一个结点已给出（k=0），故空间搜索树深度为n-1(1至n-1)
      while(k>=0){
   
           x[k]=x[k]+1; // 搜索下一个顶点编号
           while(x[k]<n){  //try{System.out.println("sdfsdf "+x[k-1]+"  "+x[k]+"  "+k);}catch(Exception e){System.out.println("sdfsdf "+"     "+x[k]+"  "+k+"");}
            if((!s[x[k]])&&(c[x[k-1]][x[k]]==1)) // 如果顶点x[k]未被使用，而且与前一结点x[k-1]之间有连线~
                 break;
            else
         x[k]=x[k]+1;  // 否则寻找下一个顶点
      }
   
       if((x[k]<n)&&(k!=n-1)){  // 搜索成功,深度加1
            s[x[k]]=true; 
        k=k+1;
       }else if((x[k]<n)&&(k==n-1)&&(c[x[k]][x[0]]==1)){ // 搜索成功,且是最后一个结点
            break;    
       }else{  // 搜索失败，回溯到前一结点，并将原结点复位
            x[k]=-1;
            k=k-1;
            s[x[k]]=false;
       }
    
  }
  
 }
 
 public static void main(String args[]){
  
  Hamilton hl=new Hamilton();
  
      int c[][]={
        {1,1,1,0,1,0},
        {1,1,1,1,0,0},
        {1,1,1,1,1,1},
        {0,1,1,1,0,1},
        {1,0,1,0,1,1},
        {0,0,1,1,1,1}
      };
      int n=6;  //6个顶点
      int x[]=new int[n];
  
      hl.hamilton(n, x, c);
  
      System.out.println("哈密尔顿回路是：");
      for(int i=0;i<n;i++)
       System.out.println("x["+i+"]="+x[i]); 
     }
}