import java.util.Vector;
class Hamilton
{
int start;
int a[][];
int len;
int x[]; // 记录回路
boolean flag;
public Hamilton(int[][] a, int n, int start)
{
this.a = a;
this.len = n;
this.flag = false;
this.x = new int[n];
this.start = start - 1;
}
public boolean isComplete(int k)
{
return a[x[k - 1]][x[0]] == 1;
}
public Vector<Integer> makeIterms(int k)
{
Vector<Integer> iterms = new Vector<Integer>();
if (k == 0)
{
iterms.add(start);
} else
{
for (int i = 0; i < len; i++)
if (a[x[k - 1]][i] == 1) // 相当重要
iterms.add(i);
}
return iterms; // 第k-1层结点的所有临界点
}
public void printSolution(int k)
{
System.out.print(x[0] + 1);
for (int i = 1; i < len; i++)
System.out.print("->" + (x[i] + 1));
System.out.println("->" + (x[0] + 1));
}
public boolean isPartial(int k)
{
for (int i = 0; i < k; i++)
if (x[i] == x[k])
return false;
return true;
}
}
class General
{
// 回溯算法的引导框架
public static void backtrack(Hamilton p)
{
explore(p, 0);
if (!p.flag)
System.out.println("no sulution!");
}
// 回溯算法的探索框架
private static void explore(Hamilton p, int k)
{
if (k >= p.len)
{
if (p.isComplete(k))
{
p.flag = true;
p.printSolution(k);
}
return;
}
Vector<Integer> iterms = p.makeIterms(k);
for (int i = 0; i < iterms.size(); i++)
{
p.x[k] = iterms.get(i);
if (p.isPartial(k))
explore(p, k + 1);
}
}
}
public class Test
{
public static void main(String args[])
{
int c[][] = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 0 },
{ 1, 0, 1, 0, 1 }, { 0, 1, 0, 1, 0 } };
Hamilton p;
p = new Hamilton(c, 5, 1);
General.backtrack(p);
}
}