Breaking
Backtracking

# Hamiltonian Cycle

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;
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] == 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```