import java.util.Scanner;
public class hamiltonian {
private boolean W[][];
private int nodeCount;
private int vindex[];
hamiltonian(int n){
nodeCount = n;
W = new boolean[nodeCount][nodeCount];
vindex = new int[nodeCount];
vindex[0] = 0;
Scanner sc = new Scanner(System.in);
char isTrue;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = i ; j <= n ; j++ ){
if ( j == i ) continue;
System.out.print(i + "노드와 " + j + "노드는 인접한가?(y/n)");
String input = sc.next();
isTrue = input.charAt(0);
if ( isTrue == 'y' ){
W[i-1][j-1] = true;
W[j-1][i-1] = true;
}
}
}
}
private boolean promising(int i){
int j;
boolean swt;
if ( i == nodeCount-1 && !W[vindex[nodeCount-1]][vindex[0]]) swt = false;
//첫번재 정점과 마지막정접의 인접성
else if ( i > 0 && !W[vindex[i-1]][vindex[i]]) swt = false;
// i번재 정점과 i-1 번째 정점은 인접
else{
swt = true;
j = 1;
while ( j < i && swt ){
if ( vindex[i] == vindex[j] ) swt = false;
//이미 선택되었는지 검사
j++;
}
}
return swt;
}
public void hamiltonianCircuit(int i){
int j;
if ( promising(i) )
if ( i == nodeCount - 1 ){
System.out.println("\nAnswer");
for ( j = 0 ; j < nodeCount ; j++ ){
System.out.print((vindex[j]+1)+" > ");
}
System.out.println((vindex[0]+1));
}else{
for ( j = 1 ; j < nodeCount ; j++ ){ //모든정점의 다음 정점을
vindex[i+1] = j; // 다시 생각해본다.
hamiltonianCircuit(i+1);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.print("정점의 개수는 ? ");
int n = sc.nextInt();
hamiltonian h = new hamiltonian(n);
h.hamiltonianCircuit(0);
}
}
- 실행화면
