A Hamiltonian cycle in a graph is a cycle that visits each vertex exactly once and returns to the starting vertex. This problem is NP-complete, meaning there is no known polynomial-time solution for all cases. However, we can use a backtracking approach to find a Hamiltonian cycle.

Program Structure

• Graph Representation: The graph is represented using an adjacency matrix.
• Backtracking Method: A recursive method is used to explore all possible paths and check if a Hamiltonian cycle exists.
• Main Method: Initializes the graph and starts the search for a Hamiltonian cycle.

Java Program

public class HamiltonianCycle {
    private int V; // Number of vertices
    private int[][] graph; // Adjacency matrix

    // Constructor to initialize the graph
    public HamiltonianCycle(int[][] graph) {
        this.graph = graph;
        this.V = graph.length;
    }

    // Utility function to check if the vertex can be added to the Hamiltonian Cycle
    private boolean isSafe(int v, int pos, int[] path) {
        // Check if this vertex is an adjacent vertex of the previously added vertex.
        if (graph[path[pos - 1]][v] == 0) {
            return false;
        }

        // Check if the vertex has already been included
        for (int i = 0; i < pos; i++) {
            if (path[i] == v) {
                return false;
            }
        }

        return true;
    }

    // Utility function to solve the Hamiltonian Cycle problem
    private boolean hamCycleUtil(int[] path, int pos) {
        // Base case: If all vertices are included in the cycle
        if (pos == V) {
            // Check if there is an edge from the last included vertex to the first vertex
            return graph[path[pos - 1]][path[0]] == 1;
        }

        // Try different vertices as the next candidate in the Hamiltonian Cycle
        for (int v = 1; v < V; v++) {
            if (isSafe(v, pos, path)) {
                path[pos] = v;

                // Recur to construct the rest of the path
                if (hamCycleUtil(path, pos + 1)) {
                    return true;
                }

                // Backtrack
                path[pos] = -1;
            }
        }

        return false;
    }

    // Function to find and print the Hamiltonian Cycle
    public void hamCycle() {
        int[] path = new int[V];
        for (int i = 0; i < V; i++) {
            path[i] = -1; // Initialize all vertices as not visited
        }

        // Let the first vertex in the path be 0
        path[0] = 0;

        if (!hamCycleUtil(path, 1)) {
            System.out.println("No Hamiltonian Cycle found.");
        } else {
            System.out.println("Hamiltonian Cycle exists: ");
            printSolution(path);
        }
    }

    // Function to print the solution
    private void printSolution(int[] path) {
        for (int i = 0; i < V; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.print(path[0]); // Print the first vertex again
        System.out.println();
    }

    // Main method to test the Hamiltonian Cycle
    public static void main(String[] args) {
        int[][] graph = {
            {0, 1, 0, 1, 0},
            {1, 0, 1, 1, 0},
            {0, 1, 0, 0, 1},
            {1, 1, 0, 0, 1},
            {0, 0, 1, 1, 0}
        };

        HamiltonianCycle hc = new HamiltonianCycle(graph);
        hc.hamCycle();
    }
}

Explanation of the Code

The program consists of several key components:

• Constructor: Initializes the adjacency matrix and the number of vertices.
• isSafe Method: Checks if a vertex can be added to the current path. It ensures that the vertex is adjacent to the last added vertex and not already included in the path.
• hamCycleUtil Method: This recursive method tries to construct a Hamiltonian cycle by exploring all possible vertices. If all vertices are included and there is an edge back to the starting vertex, it confirms a Hamiltonian cycle.
• hamCycle Method: Initializes the path and starts the recursive search. If no cycle is found, it informs the user.
• printSolution Method: Prints the Hamiltonian cycle if found.

Conclusion

This Java program provides a straightforward implementation of finding a Hamiltonian cycle in a graph using backtracking. While the solution is effective for small graphs, keep in mind that finding Hamiltonian cycles can be computationally intensive for larger graphs due to its NP-completeness.