## Introduction

In this blog, we will be discussing a backtracking problem that has been asked frequently in Interviews.

The problem is to Print all Hamiltonian Cycles in an Undirected Graph.

Before we proceed, we must understand what do we mean by backtracking and hamiltonian cycles in a graph?

**Backtracking: **Backtracking is an algorithmic technique that is used for solving the problem based on recursion by building each and every possible solution incrementally and removing those answers that fail to satisfy the problemâ€™s constraints at any time.

Let us recall what is a hamiltonian cycle?**Hamiltonian cycle: **Taking any source vertex, we have to visit all the vertices exactly once and reach back to the starting vertex without repeating any vertices.

Now letâ€™s look at the problem.

### Problem Statement

We are given an undirected graph consisting of N nodes. This graph is represented in the form of an adjacency matrix of size N X N. Our work is to print all possible hamiltonian cycles.

### Sample example

The given graph is represented as:

**Adjacency matrix representation of the given graph**

```
{ 0, 1, 1, 0, 0, 1 }
{ 1, 0, 1, 0, 1, 1 }
{ 1, 1, 0, 1, 0, 0 }
{ 0, 0, 1, 0, 1, 0 }
{ 0, 1, 0, 1, 0, 1 }
{ 1, 1, 0, 0, 1, 0 }
```

**Output:**

```
0 1 2 3 4 5 0
0 1 5 4 3 2 0
0 2 3 4 1 5 0
0 2 3 4 5 1 0
0 5 1 4 3 2 0
0 5 4 3 2 1 0
```

**Explanation for the output:**

On traversing the graph in the order 0->1->2->3->4->5->0, we can see that by traversing each and every vertex exactly once, we can reach our source (here 0). We can repeat the same by different paths also as depicted in our output.

## Approach

Now to Print all Hamiltonian Cycles in an Undirected Graph, the following approach is followed.

First, we will define a function that will check if the vertex being considered at present is not adjacent to the previous vertex and is not already included in the path.

If the above two conditions hold, the vertex is safe to be counted.

â¬‡

Next, we will define a function to find all hamiltonian cycles. All vertices of the graph will be included here, and a path must exist from the last vertex to the starting vertex.

â¬‡

We will include the source vertex in our path and print the entire path. After printing the path, we have to remove the source vertex added.

â¬‡

The above steps have to be repeated for the following vertices to find a different path.

â¬‡

All possible hamiltonian cycles will be printed. If the conditions above are not satisfied, we will mention that no hamiltonian cycles are possible.

This is our most optimised approach using backtracking. It will take O(N!) time.

Till now, I assume you have got the basic and conceptual idea of what has been mentioned in the problem statement. So, I recommend you first give it a try. __Coding Ninjas Studio__

If you were unable to solve it, donâ€™t be disappointed.

Please have a thorough look over the algorithm(pseudocode), and then again, you must try solving it.

### PseudoCode

To Print all Hamiltonian Cycles in an Undirected Graph:

___________________________________________________________________

**procedure** isSafe(int v, int graph[][6], vector<int> path, int pos):

___________________________________________________________________

**1.** If graph[path[pos - 1]][v] == 0:

return false

**2**. for ( i = 0 to pos)

if (path[i] == v): return false;

**3.** return true

**4. end procedure**

___________________________________________________________________

___________________________________________________________________

**procedure** FindHamCycle(int graph[][6], int pos, vector<int> path, bool visited[], int N):

___________________________________________________________________

**1.** if (pos == N):

if (graph[path[path.size() - 1]][path[0]] != 0):

path.push_back(0)

for (i = 0 to path.size()):

cout << path[I] << " "

path.pop_back()

hasCycle = true

return

**2**. for ( v = 0 to N):

if (isSafe(v, graph, path, pos) && !visited[v]):

path.push_back(v)

visited[v] = true

FindHamCycle(graph, pos + 1, path, visited, N)

visited[v] = false;

path.pop_back()

**3. end procedure**

___________________________________________________________________

___________________________________________________________________

**procedure** hamCycle(int graph[][6], int N):

___________________________________________________________________

**1.** hasCycle = false

**2**. vector<int> path

**3.** path.push_back(0)

**4**. bool visited[N]

**5**. for(i=0 to N):

visited[i] = false

**6**. visited[0] = true

**7**. FindHamCycle(graph, 1, path, visited, N)

**8**. if (!hasCycle): cout << "No Hamiltonian Cycle" << "possible " << endl

**9. end procedure**

___________________________________________________________________