Java を使用してグラフのハミルトニアン サイクル アルゴリズムを実装する方法

class Graph {
    private int[][] adjacencyMatrix;
    private int numVertices;

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
    }

    public void addEdge(int start, int end) {
        adjacencyMatrix[start][end] = 1;
        adjacencyMatrix[end][start] = 1;
    }

    public boolean isConnected(int start, int end) {
        return adjacencyMatrix[start][end] == 1;
    }
}

class HamiltonianCycle {
    private Graph graph;
    private int numVertices;
    private int[] path;

    public HamiltonianCycle(Graph graph) {
        this.graph = graph;
        this.numVertices = graph.getNumVertices();
        this.path = new int[numVertices];
        // 将路径初始化为-1，表示顶点还未被遍历
        for (int i = 0; i < numVertices; i++) {
            path[i] = -1;
        }
    }

    public void findHamiltonianCycle() {
        path[0] = 0; // 从顶点0开始
        if (findFeasibleSolution(1)) {
            printSolution();
        } else {
            System.out.println("No solution exists.");
        }
    }

    private boolean findFeasibleSolution(int position) {
        if (position == numVertices) {
            int start = path[position - 1];
            int end = path[0];
            if (graph.isConnected(start, end)) {
                return true;
            } else {
                return false;
            }
        }

        for (int vertex = 1; vertex < numVertices; vertex++) {
            if (isFeasible(vertex, position)) {
                path[position] = vertex;
                if (findFeasibleSolution(position + 1)) {
                    return true;
                }
                // 回溯
                path[position] = -1;
            }
        }
        return false;
    }

    private boolean isFeasible(int vertex, int actualPosition) {
        // 两个相邻顶点之间必须是连通的
        if (!graph.isConnected(path[actualPosition - 1], vertex)) {
            return false;
        }
        // 该顶点是否已经在路径中
        for (int i = 0; i < actualPosition; i++) {
            if (path[i] == vertex) {
                return false;
            }
        }
        return true;
    }

    private void printSolution() {
        System.out.println("Hamiltonian Cycle exists:");
        for (int i = 0; i < numVertices; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println(path[0]);
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);

        HamiltonianCycle hamiltonianCycle = new HamiltonianCycle(graph);
        hamiltonianCycle.findHamiltonianCycle();
    }
}