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. |