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

Implementation of Hamiltonian Cycle using C Programming Language

#include <stdio.h> #define V 5 // Function to check if the vertex v can be added to the current path int isSafe(int v, int graph[V][V], int path[], int pos) { // Check if this vertex is adjacent to the previously added vertex if (graph[path[pos - 1]][v] == 0) return 0; // Check if the vertex is already included in the path for (int i = 0; i < pos; i++) if (path[i] == v) return 0; return 1; } // A recursive utility function to solve the Hamiltonian Cycle problem int hamiltonianCycleUtil(int graph[V][V], int path[], int pos) { // Base case: If all vertices are included in the path if (pos == V) { // And if there is an edge from the last vertex to the first vertex if (graph[path[pos - 1]][path[0]] == 1) return 1; else return 0; } // Try different vertices as the next candidate in the Hamiltonian cycle for (int v = 1; v < V; v++) { if (isSafe(v, graph, path, pos)) { path[pos] = v; // Recur to construct the rest of the path if (hamiltonianCycleUtil(graph, path, pos + 1) == true) return 1; // If adding vertex v doesn't lead to a solution, remove it (backtrack) path[pos] = -1; } } return 0; } // This function solves the Hamiltonian Cycle problem using Backtracking int hamiltonianCycle(int graph[V][V]) { int path[V]; for (int i = 0; i < V; i++) path[i] = -1; // Start from the first vertex path[0] = 0; if (hamiltonianCycleUtil(graph, path, 1) == false) { printf("No Hamiltonian Cycle found\n"); return 0; } printf("Hamiltonian Cycle found: "); for (int i = 0; i < V; i++) printf("%d ", path[i]); printf("%d\n", path[0]); // To show the cycle return 1; } // Driver program to test above functions int main() { /* Let us create the following graph (0)--(1)--(2) | / \ | | / \ | | / \ | (3)-------(4) */ int graph[V][V] = { {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} }; hamiltonianCycle(graph); return 0; }

---

Happy Exploring!