Table Of Contents

show

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 return 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 check if the vertex has already been visited or is adjacent to previously added vertex.
- If any such vertex is found, add it to the array and backtrack from that node.
- Try every possible combinations and if a path returns false, ignore the vertex and start iterating from the next vertex till all the nodes has been visited.

**Implementation of the Approach:**

### C++ Code

#define N 8 //vertices char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}; //adjacency matrix 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 to explore more hamiltonian cycles 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[]; //adjacency matrix int adjacencyM[][]; //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.adjacencyM = adjacencyM; 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 to explore more hamiltonian cycles 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) { names.add(vertices[idx]); } System.out.println(names); } } class Main { public static void main(String[] args) { //vertices char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}; //adjacency matrix 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 to explore more cycles 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.

**Practice Questions:**

## FAQ

**What is the time and space complexity of the backtracking approach?**The time and space complexity of the backtracking approach. is O(N!) and O(1), where N is the number of vertices.**What is a Hamiltonian Cycle?**A**Hamiltonian Cycle**is a cycle that traverses all the nodes of the graph exactly once and return back to the starting point.