# Hamiltonian Path Problem

## Problem Statement:

Given an undirected graph. The task is to print all the Hamiltonian cycles present in the graph.

A Hamiltonian Cycle is a cycle that traverses all the nodes of the graph exactly once and returns back to the starting point.

Example :

Input :

## Approach: Backtracking

The problem can be solved using a backtracking approach. Follow the below steps to solve the problem.

Algorithm:

• Create an empty path array.
• Add the vertex 0 to the array.
• Start adding vertex 1 and other connected nodes and check if the current vertex can be included in the array or not.
• This can be done by using a visiting array and checking if the vertex has already been visited or is adjacent to the previously added vertex.
• If any such vertex is found, add it to the array and backtrack from that node.
• Try every possible combination and if a path returns false, ignore the vertex and start iterating from the next vertex till all the nodes have been visited.

Implementation of the Approach:

### C++ Code

```#define N 8
//vertices
char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
int adjacencyM[N][N]= {{0, 1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0}};

//list mapping of vertices to mark vertex visited
int visited[N] {
0
};

class Hamiltonian {
public:
//start (& end) vertex
int start;
//stack used as list to store the path of the cycle
list < int > cycle;
//variable to mark if graph has the cycle
bool hasCycle = false;
//constructor
Hamiltonian(int start) {
this -> start = start;
}

//method to initiate the search of the Hamiltonian cycle
void findCycle() {
//add starting vertex to the list
cycle.push_back(start);

//start searching the path
solve(start);
}

void solve(int vertex) {
//Base condition: if the vertex is the start vertex
//and all nodes have been visited (start vertex twice)
if (vertex == start && cycle.size() == N + 1) {
hasCycle = true;

//output the cycle
displayCycle();

return;
}

//iterate through the neighbor vertices
for (int i = 0; i < N; i++) {
if (adjacencyM[vertex][i] == 1 && visited[i] == 0) {
int nbr = i;
//visit and add vertex to the cycle
visited[nbr] = 1;
cycle.push_back(nbr);

//Go to the neighbor vertex to find the cycle
solve(nbr);
//Backtrack
visited[nbr] = 0;
cycle.pop_back();
}
}
}

//Function to display hamiltonian cycle
void displayCycle() {
cout << "[";
for (int v: cycle) {
cout << vertices[v] << " ";
}
cout << "] \n";
}
};```

### Java Code

``` class Hamiltonian {
//vertices
char vertices[];
//list mapping of vertices to mark vertex visited
int visited[];
//start (& end) vertex index
int start;
//stack used as list to store the path of the cycle
Stack < Integer > cycle = new Stack < > ();
//number of vertices in the graph
int N;
//variable to mark if graph has the cycle
boolean hasCycle = false;

//constructor
Hamiltonian(int start, char vertices[], int adjacencyM[][]) {
this.start = start;
this.vertices = vertices;
this.N = vertices.length;
this.visited = new int[vertices.length];
}

//method to initiate the search of the Hamiltonian cycle
public void findCycle() {
//add starting vertex to the list
cycle.push(start);

//start searching the path
solve(start);
}

private void solve(int vertex) {
//Base condition: if the vertex is the start vertex
//and all nodes have been visited (start vertex twice)
if (vertex == start && cycle.size() == N + 1) {
hasCycle = true;

//output the cycle
displayCycle();

return;
}

//iterate through the neighbor vertices
for (int i = 0; i < N; i++) {
if (adjacencyM[vertex][i] == 1 && visited[i] == 0) {
int nbr = i;
//visit and add vertex to the cycle
visited[nbr] = 1;
cycle.push(nbr);

//Go to the neighbor vertex to find the cycle
solve(nbr);

//Backtrack
visited[nbr] = 0;
cycle.pop();
}
}
}

//Method to display the path of the cycle
void displayCycle() {
//converting vertex index to the name
List < Character > names = new ArrayList < > ();
for (int idx: cycle) {
}
System.out.println(names);
}
}
class Main {
public static void main(String[] args) {
//vertices
char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
int adjacencyM[][]= {{0, 1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 0, 1, 0}};

//Driver code
Hamiltonian hamiltonian = new Hamiltonian(0,vertices, adjacencyM);
hamiltonian.findCycle();

//if the graph doesn't have any Hamiltonian Cycle
if(!hamiltonian.hasCycle){
System.out.println("No Hamiltonian Cycle");
}
}
}```

### Python Code

```class Hamiltonian:
def __init__(self, start):
# start (& end) vertex
self.start = start

# list to store the cycle path
self.cycle = []

# variable to mark if graph has the cycle
self.hasCycle = False

# method to initiate the search of cycle
def findCycle(self):
# add starting vertex to the list
self.cycle.append(self.start)

# start the search of the hamiltonian cycle
self.solve(self.start)

# recursive function to implement backtracking
def solve(self, vertex):
# Base condition: if the vertex is the start vertex
# and all nodes have been visited (start vertex twice)
if vertex == self.start and len(self.cycle) == N + 1:
self.hasCycle = True

# output the cycle
self.displayCycle()

return

# iterate through the neighbor vertices
for i in range(len(vertices)):
if adjacencyM[vertex][i] == 1 and visited[i] == 0:
nbr = i
# visit and add vertex to the cycle
visited[nbr] = 1
self.cycle.append(nbr)

# traverse the neighbor vertex to find the cycle
self.solve(nbr)

# Backtrack
visited[nbr] = 0
self.cycle.pop()

# function to display the hamiltonian class
def displayCycle(self):
names = []
for v in self.cycle:
names.append(vertices[v])
print(names)

if __name__ == '__main__':
vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
adjacencyM = [[0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0]]
#list mapping of vertices to mark vertex visited
visited = [0 for x in range(len(vertices))]

#number of vertices in the graph
N = 8

#Driver code
hamiltonian = Hamiltonian(0)
hamiltonian.findCycle()

#if the graph doesn't have any Hamiltonian Cycle
if not hamiltonian.hasCycle:
print("No Hamiltonian Cycle")```
• Time Complexity: O(N!), where N is the number of vertices.
• Space Complexity: O(1), as no extra space is used.

## FAQ

### Q.1: What is the time and space complexity of the backtracking approach?

Ans: The time and space complexity of the backtracking approach. is O(N!) and O(1), where N is the number of vertices.

### Q.2: What is a Hamiltonian Cycle?

Ans: A Hamiltonian Cycle is a cycle that traverses all the nodes of the graph exactly once and returns back to the starting point.

##### Previous Post ## Balanced Binary Tree

##### Next Post 