Hamiltonian Cycle using Backtracking

A Hamiltonian graph is the directed or undirected graph containing a Hamiltonian cycle. The Hamiltonian cycle is the cycle that traverses all the vertices of the given graph G exactly once and then ends at the starting vertex.

The input for the Hamiltonian graph problem can be the directed or undirected graph. The Hamiltonian problem involves checking if the Hamiltonian cycle is present in a graph G or not. The following graph illustrates the presence of the Hamiltonian cycle in a graph G.

While generating the state space tree following bounding functions are to be considered, which are as follows:

• The ith vertex in the path must be adjacent to the (i-1)th vertex in any path.
• The starting vertex and the (n-1)th vertex should be adjacent.
• The ith vertex cannot be one of the first (i-1)th vertex in the path.

This algorithm uses the recursive formulated of backtracking to find all the Hamiltonian cycles of a graph. The graph is stored as an adjacency matrix G [1: n, 1: n].

In the next value k, x [1: k-1] is a path with k-1 distinct vertices. if x[k] == 0 then no vertex has to be yet been assign to x[k]. After execution x[k] is assigned to the next highest numbered vertex which does not already appear in the path x [1: k-1] and is connected by an edge to x [k – 1] otherwise x[k] == 0.

If k == n, (here n is the number of vertices) then in addition x[n] is connected to x [1].

---

Happy Exploring!