Hamiltonian Cycle
What is a Hamiltonian Cycle?
A Hamiltonian Cycle or Circuit is a path in a graph that visits every vertex exactly once and returns to the starting vertex, forming a closed loop. A graph is said to be a Hamiltonian graph only when it contains a hamiltonian cycle, otherwise, it is called non-Hamiltonian graph.
A graph is an abstract data type (ADT) consisting of a set of objects that are connected via links.
The practical applications of hamiltonian cycle problem can be seen in the fields like network design, delivery systems and many more. However, the solution to this problem can be found only for small types of graphs, and not for larger ones.
Input Output Scenario
Suppose the given undirected graph G(V, E) and its adjacency matrix are as follows −
The backtracking algorithm can be used to find a Hamiltonian path in the above graph. If found, the algorithm returns the path. If not, it returns false. For this case, the output should be (0, 1, 2, 4, 3, 0).
Finding Hamiltonian Cycle using Backtracking Approach
The naive way to solve Hamiltonian cycle problem is by generating all possible configurations of vertices and checking if any configuration satisfies the given constraints. However, this approach is not suitable for large graphs as its time complexity will be (O(N!)).
The following steps explain the working of backtracking approach −
First, create an empty path array and add a starting vertex 0 to it.
Next, start with vertex 1 and then add other vertices one by one.
While adding vertices, check whether a given vertex is adjacent to the previously added vertex and hasn't been added already.
If any such vertex is found, add it to the path as part of the solution, otherwise, return false.
Example
The following example demonstrates how to find a hamiltonian cycle within a given undirected graph.
#include <stdio.h>
#define NODE 5
int graph[NODE][NODE] = {
{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},
};
int path[NODE];
// Function to display the Hamiltonian cycle
void displayCycle() {
printf("Cycle Found: ");
for (int i = 0; i < NODE; i++)
printf("%d ", path[i]);
// Print the first vertex again
printf("%d
", path[0]);
}
// Function to check if adding vertex v to the path is valid
int isValid(int v, int k) {
// If there is no edge between path[k-1] and v
if (graph[path[k - 1]][v] == 0)
return 0;
// Check if vertex v is already taken in the path
for (int i = 0; i < k; i++)
if (path[i] == v)
return 0;
return 1;
}
// Function to find the Hamiltonian cycle
int cycleFound(int k) {
// When all vertices are in the path
if (k == NODE) {
// Check if there is an edge between the last and first vertex
if (graph[path[k - 1]][path[0]] == 1)
return 1;
else
return 0;
}
// Try adding each vertex (except the starting point) to the path
for (int v = 1; v < NODE; v++) {
if (isValid(v, k)) {
path[k] = v;
if (cycleFound(k + 1) == 1)
return 1;
// Backtrack: Remove v from the path
path[k] = -1;
}
}
return 0;
}
// Function to find and display the Hamiltonian cycle
int hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
// Set the first vertex as 0
path[0] = 0;
if (cycleFound(1) == 0) {
printf("Solution does not exist
");
return 0;
}
displayCycle();
return 1;
}
int main() {
hamiltonianCycle();
return 0;
}
#include <iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{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},
};
int path[NODE];
// Function to display the Hamiltonian cycle
void displayCycle() {
cout << "Cycle Found: ";
for (int i = 0; i < NODE; i++)
cout << path[i] << " ";
// Print the first vertex again
cout << path[0] << endl;
}
// Function to check if adding vertex v to the path is valid
bool isValid(int v, int k) {
// If there is no edge between path[k-1] and v
if (graph[path[k - 1]][v] == 0)
return false;
// Check if vertex v is already taken in the path
for (int i = 0; i < k; i++)
if (path[i] == v)
return false;
return true;
}
// function to find the Hamiltonian cycle
bool cycleFound(int k) {
// When all vertices are in the path
if (k == NODE) {
// Check if there is an edge between the last and first vertex
if (graph[path[k - 1]][path[0]] == 1)
return true;
else
return false;
}
// adding each vertex to the path
for (int v = 1; v < NODE; v++) {
if (isValid(v, k)) {
path[k] = v;
if (cycleFound(k + 1) == true)
return true;
// Remove v from the path
path[k] = -1;
}
}
return false;
}
// Function to find and display the Hamiltonian cycle
bool hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
// Set the first vertex as 0
path[0] = 0;
if (cycleFound(1) == false) {
cout << "Solution does not exist" << endl;
return false;
}
displayCycle();
return true;
}
int main() {
hamiltonianCycle();
}
public class HamiltonianCycle {
static final int NODE = 5;
static int[][] 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}
};
static int[] path = new int[NODE];
// method to display the Hamiltonian cycle
static void displayCycle() {
System.out.print("Cycle Found: ");
for (int i = 0; i < NODE; i++)
System.out.print(path[i] + " ");
// Print the first vertex again
System.out.println(path[0]);
}
// method to check if adding vertex v to the path is valid
static boolean isValid(int v, int k) {
// If there is no edge between path[k-1] and v
if (graph[path[k - 1]][v] == 0)
return false;
// Check if vertex v is already taken in the path
for (int i = 0; i < k; i++)
if (path[i] == v)
return false;
return true;
}
// method to find the Hamiltonian cycle
static boolean cycleFound(int k) {
// When all vertices are in the path
if (k == NODE) {
// Check if there is an edge between the last and first vertex
if (graph[path[k - 1]][path[0]] == 1)
return true;
else
return false;
}
// adding each vertex (except the starting point) to the path
for (int v = 1; v < NODE; v++) {
if (isValid(v, k)) {
path[k] = v;
if (cycleFound(k + 1))
return true;
// Remove v from the path
path[k] = -1;
}
}
return false;
}
// method to find and display the Hamiltonian cycle
static boolean hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
// Set the first vertex as 0
path[0] = 0;
if (!cycleFound(1)) {
System.out.println("Solution does not exist");
return false;
}
displayCycle();
return true;
}
public static void main(String[] args) {
hamiltonianCycle();
}
}
NODE = 5
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]
]
path = [None] * NODE
# Function to display the Hamiltonian cycle
def displayCycle():
print("Cycle Found:", end=" ")
for i in range(NODE):
print(path[i], end=" ")
# Print the first vertex again
print(path[0])
# Function to check if adding vertex v to the path is valid
def isValid(v, k):
# If there is no edge between path[k-1] and v
if graph[path[k - 1]][v] == 0:
return False
# Check if vertex v is already taken in the path
for i in range(k):
if path[i] == v:
return False
return True
# Function to find the Hamiltonian cycle
def cycleFound(k):
# When all vertices are in the path
if k == NODE:
# Check if there is an edge between the last and first vertex
if graph[path[k - 1]][path[0]] == 1:
return True
else:
return False
# adding each vertex (except the starting point) to the path
for v in range(1, NODE):
if isValid(v, k):
path[k] = v
if cycleFound(k + 1):
return True
# Remove v from the path
path[k] = None
return False
# Function to find and display the Hamiltonian cycle
def hamiltonianCycle():
for i in range(NODE):
path[i] = None
# Set the first vertex as 0
path[0] = 0
if not cycleFound(1):
print("Solution does not exist")
return False
displayCycle()
return True
if __name__ == "__main__":
hamiltonianCycle()
Output
Cycle Found: 0 1 2 4 3 0
