Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Hamiltonian Path problem is actually looking for a longest simple path in a graph. This is a classic NP-complete problem.
Write a program to find the Hamiltonian Cycle.
source Code
package com.dsacode.Algorithm.backtracking; import java.util.Arrays; public class HamiltonianCycle { private int V, pathCount; private int[] path; private int[][] graph; public HamiltonianCycle(int V){ this.V=V; } public void findHamiltonianCycle(int[][] g) { graph = g; path = new int[graph.length]; Arrays.fill(path, -1); try { path[0] = 0; pathCount = 1; solve(0); System.out.println("No solution"); } catch (Exception e) { System.out.println(e.getMessage()); display(); } } public void solve(int vertex) throws Exception { if (graph[vertex][0] == 1 && pathCount == graph.length) throw new Exception("Hamiltonian Cycle Solution found"); if (pathCount == graph.length) return; for (int v = 0; v < graph.length; v++) { if (graph[vertex][v] == 1) { path[pathCount++] = v; graph[vertex][v] = 0; graph[v][vertex] = 0; if (!isPresent(v)) solve(v); graph[vertex][v] = 1; graph[v][vertex] = 1; path[--pathCount] = -1; } } } public boolean isPresent(int v) { for (int i = 0; i < pathCount - 1; i++) if (path[i] == v) return true; return false; } public void display() { System.out.print("Display the Hamiltonian Cycle Path : "); for (int i = 0; i <= V; i++) if(i==V) System.out.print(path[i % V]); else System.out.print(path[i % V] + "-> "); System.out.println(); } public static void main(String[] args) { HamiltonianCycle hc = new HamiltonianCycle(5); int[][] graph1 = {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 1}, {0, 1, 1, 1, 0}, }; System.out.println("Print the values from graph: "+Arrays.deepToString(graph1)); hc.findHamiltonianCycle(graph1); } }
Output
Print the values from graph: [[0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 0, 1], [1, 1, 0, 0, 1], [0, 1, 1, 1, 0]] Hamiltonian Cycle Solution found Display the Hamiltonian Cycle Path: 0-> 1-> 2-> 4-> 3-> 0
Algorithm Explanation
![]() | Give two dimension array of elements, Function to find cycle and find paths recursively. |
![]() | Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. |
![]() | Check for whether it is adjacent to the previously added vertex and not already added. |
![]() | If it finds such a vertex, we add the vertex as part of the solution. Otherwise, return false. |