Problem: Given an undirected graph, find and print all the Hamiltonian Cycles present in the graph.

## What is the Hamiltonian cycle?

A Hamiltonian cycle also called a Hamiltonian circuit, is a graph cycle (i.e., closed-loop) through a graph that visits each node exactly once.

## How to Find the Hamiltonian Cycle using Backtracking?

Using the backtracking method, we can easily find all the Hamiltonian Cycles present in the given graph.

The idea is to use the Depth-First Search algorithm to traverse the graph until all the vertices have been visited.

We traverse the graph starting from a vertex (arbitrary vertex chosen as starting vertex) and

At any point during the traversal we get stuck (i.e., all the neighbor vertices have been visited), we backtrack to find other paths (i.e., to visit another unvisited vertex).

If we successfully reach back to the starting vertex after visiting all the nodes, it means the graph has a Hamiltonian cycle otherwise not.

We mark each vertex as visited so that we don’t traverse them more than once.

## Print All Hamiltonian Cycles present in the Graph (represented using Adjacency Matrix)

Adjacency Matrix is a 2D array that indicates whether the pair of nodes are adjacent or not in the graph.

Since adjacency matrix is an array, we will also represent the vertices as an array elements in our program.

### Java

Output:

[A, B, C, D, E, F, G, H, A]
[A, H, G, F, E, D, C, B, A]

The `solve()` method of the `Hamiltonian` class is the recursive method implementing the backtracking algorithm.

As discussed, using DFS we traverse the graph, and every time we find a cycle (i.e., the base condition is satisfied), we output it and deliberately backtrack (i.e., return) to find more such cycles.

If the given graph does have any Hamiltonian cycle, the value of the `hasCycle` variable remains `false`. We use it in our main method to print output the respective result.

## Print All Hamiltonian Cycles present in the Graph (represented using Adjacency List)

When a graph is represented using adjacency lists, every vertex holds a list that describes the set of its neighbor’s vertices.

In our program, we represent the vertex as a class with an adjacency list as it’s one of its properties and construct the graph by adding the connected vertices to their respective adjacency lists.

### Java

Output:

[A, B, C, D, E, F, G, H, A]
[A, H, G, F, E, D, C, B, A]

The output contains the paths of the Hamiltonian cycles present in the given undirected graph.

In this tutorial, we learned what Hamiltonian Cycle is and how to find and print all Hamiltonian cycles present in an undirected graph using the backtracking algorithm.