되추적 해밀토니안

public class Main
{
    int n;
	int[] path;
	public static void main(String[] args) 
	{
	    Main hamil = new Main();
	    hamil.path = new int[10];
	    
	    int[][] G = {
	        {0,1,1,1},
	        {1,0,0,1},
	        {1,0,0,1},
	        {1,1,1,0}
	    };
	    
	    hamil.n = 4;
	    hamil.path[0] = 1; // 시작 정점을 1로
	    hamil.hamiltonian(G, 0);
	    for (int i=0; i<5; i++)
	    {
	        System.out.println(hamil.path[i]);
	    }
	}
	
	public void hamiltonian(int[][] G, int i)
	{ // 연결된 무방향 그래프내의 모든 해밀토니안 회로를 찾아서 출력
	    int j;
	    if (valid(G, i)) // 유효하면
	    {
	        if (i == n-1) // 찾은 해밀토니안 회로 path[0,... n-1]을 출력
	        {
	            System.out.print("찾은 해밀토니안 회로: ");
	            for (i=0; i<n; i++)
	            {
	                System.out.print(path[i] + "->");
	            }
	            System.out.println(path[0]);
	            return;
	        }
	        else
	        { // i번째로 방문할 정점으로 시작정점이 아닌 모든 정점을 시도
	            for (j=2; j<=n; j++)
	            {
	                path[i+1] = j; // 겹치면 안됨.
	                //System.out.println("path[" + (i+1) + "] = " + j + ", n = " + n);
	                hamiltonian(G, i+1);
	            }
	        }
	    }
	}
	    
    public boolean valid(int[][] G, int i)
    { // 경로상 i번째 정점이 유효한 선택인지 확인
        int j;
        
        if ((i == n-1) && (G[path[n-1]-1][path[0]-1] == 0))
        { // 마지막 노드가 첫번째 정점과 인접하지 않는 경우
            return false;
        }
        else if ((i>0) && (G[path[i-1]-1][path[i]-1] == 0))
        { // i번째와 i-1번쨰 노드가 인접하지 않는 경우
            return false;
        }
        else 
        { // i번째 정점이 이미 선택되었는지 확인
           j=1;
           while (j<i)
           {
               if (path[i] == path[j])
               {
                   return false;
               }
               j++;
           }
           return true;
        }
    }
}