哈密顿回路算法java

哈密顿回路算法（Hamiltonian cycle algorithm）是解决哈密顿回路问题的一种算法。该问题是指在给定的无向图中是否存在一条简单回路，经过每个顶点恰好一次。以下是一个简单的Java实现：

public class HamiltonianCycle {
    private int numOfVertexes;
    private int[] hamiltonianPath;
    private int[][] adjacencyMatrix;
 
    public HamiltonianCycle(int[][] adjacencyMatrix) {
        this.adjacencyMatrix = adjacencyMatrix;
        this.numOfVertexes = adjacencyMatrix.length;
        this.hamiltonianPath = new int[numOfVertexes];
        this.hamiltonianPath[0] = 0;
    }
 
    public void solve() {
        if (findFeasibleSolution(1)) {
            printHamiltonianPath();
        } else {
            System.out.println("No feasible solution found");
        }
    }
 
    private boolean findFeasibleSolution(int position) {
        if (position == numOfVertexes) {
            if (adjacencyMatrix[hamiltonianPath[position - 1]][hamiltonianPath[0]] == 1) {
                return true;
            } else {
                return false;
            }
        }
        for (int vertexIndex = 1; vertexIndex < numOfVertexes; ++vertexIndex) {
            if (isFeasible(vertexIndex, position)) {
                hamiltonianPath[position] = vertexIndex;
                if (findFeasibleSolution(position + 1)) {
                    return true;
                }
                //backtrack
            }
        }
        return false;
    }
 
    private boolean isFeasible(int vertexIndex, int actualPosition) {
        // first criterion: whether the two nodes are connected?
        if (adjacencyMatrix[hamiltonianPath[actualPosition - 1]][vertexIndex] == 0) {
            return false;
        }
        // second criterion: whether we have already added this given node?
        for (int i = 0; i < actualPosition; ++i) {
            if (hamiltonianPath[i] == vertexIndex) {
                return false;
            }
        }
        return true;
    }
 
    private void printHamiltonianPath() {
        System.out.print("Hamiltonian cycle: ");
        for (int i = 0; i < numOfVertexes; ++i) {
            System.out.print(hamiltonianPath[i] + " ");
        }
        System.out.println(hamiltonianPath[0]);
    }
}

这个实现中，我们使用邻接矩阵来表示图，并且在每一步中使用回溯算法来寻找哈密顿回路。