- Problem Statement:<\/a><\/li>
- Approach: Backtracking<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- Practice Questions:<\/a><\/li>
- FAQ<\/a><\/li>
- Q.1: What is the time and space complexity of the backtracking approach?<\/a><\/li>
- Q.2: What is a Hamiltonian Cycle?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement:<\/h2>\n\n\n\n
Given an undirected graph. <\/strong>The task is to print all the Hamiltonian cycles present in the graph.<\/p>\n\n\n\n
A Hamiltonian Cycle<\/strong> is a cycle that traverses all the nodes of the graph exactly once and returns back to the starting point.<\/p>\n\n\n\n
<\/figure>\n\n\n\n
Example :<\/strong><\/p>\n\n\n\n
Input :<\/strong><\/p>\n\n\n\n
Approach: Backtracking<\/h2>\n\n\n\n
The problem can be solved using a backtracking approach. Follow the below steps to solve the problem.<\/p>\n\n\n\n
Algorithm:<\/strong><\/p>\n\n\n\n
- Create an empty path array.<\/li>
- Add the vertex 0 to the array.<\/li>
- Start adding vertex 1 and other connected nodes and check if the current vertex can be included in the array or not.<\/li>
- 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.<\/li>
- If any such vertex is found, add it to the array and backtrack from that node.<\/li>
- 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.<\/li><\/ul>\n\n\n\n
Implementation of the Approach:<\/strong><\/p>\n\n\n\n
C++ Code<\/h3>\n\n\n\n
#define N 8\n\/\/vertices\nchar vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};\n\/\/adjacency matrix\nint adjacencyM[N][N]= {{0, 1, 0, 0, 0, 0, 0, 1},\n {1, 0, 1, 0, 0, 0, 0, 0},\n {0, 1, 0, 1, 0, 0, 0, 1},\n {0, 0, 1, 0, 1, 0, 1, 0},\n {0, 0, 0, 1, 0, 1, 0, 0},\n {0, 0, 0, 0, 1, 0, 1, 0},\n {0, 0, 0, 1, 0, 1, 0, 1},\n {1, 0, 1, 0, 0, 0, 1, 0}};\n \n\/\/list mapping of vertices to mark vertex visited\nint visited[N] {\n 0\n};\n \nclass Hamiltonian {\n public:\n \/\/start (& end) vertex\n int start;\n \/\/stack used as list to store the path of the cycle\n list < int > cycle;\n \/\/variable to mark if graph has the cycle\n bool hasCycle = false;\n\/\/constructor\n Hamiltonian(int start) {\n this -> start = start;\n }\n \n \/\/method to initiate the search of the Hamiltonian cycle\n void findCycle() {\n \/\/add starting vertex to the list\n cycle.push_back(start);\n \n \/\/start searching the path\n solve(start);\n }\n \n void solve(int vertex) {\n \/\/Base condition: if the vertex is the start vertex\n \/\/and all nodes have been visited (start vertex twice)\n if (vertex == start && cycle.size() == N + 1) {\n hasCycle = true;\n \n \/\/output the cycle\n displayCycle();\n \n \/\/return to explore more hamiltonian cycles\n return;\n }\n \n \/\/iterate through the neighbor vertices\n for (int i = 0; i < N; i++) {\n if (adjacencyM[vertex][i] == 1 && visited[i] == 0) {\n int nbr = i;\n \/\/visit and add vertex to the cycle\n visited[nbr] = 1;\n cycle.push_back(nbr);\n \n \/\/Go to the neighbor vertex to find the cycle\n solve(nbr);\n \/\/Backtrack\n visited[nbr] = 0;\n cycle.pop_back();\n }\n }\n }\n \n \/\/Function to display hamiltonian cycle\n void displayCycle() {\n cout << \"[\";\n for (int v: cycle) {\n cout << vertices[v] << \" \";\n }\n cout << \"] \\n\";\n }\n};<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
class Hamiltonian {\n \/\/vertices\n char vertices[];\n \/\/adjacency matrix\n int adjacencyM[][];\n \/\/list mapping of vertices to mark vertex visited\n int visited[];\n \/\/start (& end) vertex index\n int start;\n \/\/stack used as list to store the path of the cycle\n Stack < Integer > cycle = new Stack < > ();\n \/\/number of vertices in the graph\n int N;\n \/\/variable to mark if graph has the cycle\n boolean hasCycle = false;\n \n \/\/constructor\n Hamiltonian(int start, char vertices[], int adjacencyM[][]) {\n this.start = start;\n this.vertices = vertices;\n this.adjacencyM = adjacencyM;\n this.N = vertices.length;\n this.visited = new int[vertices.length];\n }\n \n \/\/method to initiate the search of the Hamiltonian cycle\n public void findCycle() {\n \/\/add starting vertex to the list\n cycle.push(start);\n \n \/\/start searching the path\n solve(start);\n }\n \n private void solve(int vertex) {\n \/\/Base condition: if the vertex is the start vertex\n \/\/and all nodes have been visited (start vertex twice)\n if (vertex == start && cycle.size() == N + 1) {\n hasCycle = true;\n \n \/\/output the cycle\n displayCycle();\n \n \/\/return to explore more hamiltonian cycles\n return;\n }\n \n \/\/iterate through the neighbor vertices\n for (int i = 0; i < N; i++) {\n if (adjacencyM[vertex][i] == 1 && visited[i] == 0) {\n int nbr = i;\n \/\/visit and add vertex to the cycle\n visited[nbr] = 1;\n cycle.push(nbr);\n \n \/\/Go to the neighbor vertex to find the cycle\n solve(nbr);\n \n \/\/Backtrack\n visited[nbr] = 0;\n cycle.pop();\n }\n }\n }\n \n \/\/Method to display the path of the cycle\n void displayCycle() {\n \/\/converting vertex index to the name\n List < Character > names = new ArrayList < > ();\n for (int idx: cycle) {\n names.add(vertices[idx]);\n }\n System.out.println(names);\n }\n}\nclass Main {\n public static void main(String[] args) {\n \/\/vertices\n char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};\n \/\/adjacency matrix\n int adjacencyM[][]= {{0, 1, 0, 0, 0, 0, 0, 1},\n {1, 0, 1, 0, 0, 0, 0, 0},\n {0, 1, 0, 1, 0, 0, 0, 1},\n {0, 0, 1, 0, 1, 0, 1, 0},\n {0, 0, 0, 1, 0, 1, 0, 0},\n {0, 0, 0, 0, 1, 0, 1, 0},\n {0, 0, 0, 1, 0, 1, 0, 1},\n {1, 0, 1, 0, 0, 0, 1, 0}};\n \n \/\/Driver code\n Hamiltonian hamiltonian = new Hamiltonian(0,vertices, adjacencyM);\n hamiltonian.findCycle();\n \n \/\/if the graph doesn't have any Hamiltonian Cycle\n if(!hamiltonian.hasCycle){\n System.out.println(\"No Hamiltonian Cycle\");\n }\n }\n}<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
class Hamiltonian:\n def __init__(self, start):\n # start (& end) vertex\n self.start = start\n \n # list to store the cycle path\n self.cycle = []\n \n # variable to mark if graph has the cycle\n self.hasCycle = False\n \n # method to initiate the search of cycle\n def findCycle(self):\n # add starting vertex to the list\n self.cycle.append(self.start)\n \n # start the search of the hamiltonian cycle\n self.solve(self.start)\n \n # recursive function to implement backtracking\n def solve(self, vertex):\n # Base condition: if the vertex is the start vertex\n # and all nodes have been visited (start vertex twice)\n if vertex == self.start and len(self.cycle) == N + 1:\n self.hasCycle = True\n \n # output the cycle\n self.displayCycle()\n \n # return to explore more cycles\n return\n \n # iterate through the neighbor vertices\n for i in range(len(vertices)):\n if adjacencyM[vertex][i] == 1 and visited[i] == 0:\n nbr = i\n # visit and add vertex to the cycle\n visited[nbr] = 1\n self.cycle.append(nbr)\n \n # traverse the neighbor vertex to find the cycle\n self.solve(nbr)\n \n # Backtrack\n visited[nbr] = 0\n self.cycle.pop()\n \n # function to display the hamiltonian class\n def displayCycle(self):\n names = []\n for v in self.cycle:\n names.append(vertices[v])\n print(names)\n \nif __name__ == '__main__':\n vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']\n adjacencyM = [[0, 1, 0, 0, 0, 0, 0, 1],\n [1, 0, 1, 0, 0, 0, 0, 0],\n [0, 1, 0, 1, 0, 0, 0, 1],\n [0, 0, 1, 0, 1, 0, 1, 0],\n [0, 0, 0, 1, 0, 1, 0, 0],\n [0, 0, 0, 0, 1, 0, 1, 0],\n [0, 0, 0, 1, 0, 1, 0, 1],\n [1, 0, 1, 0, 0, 0, 1, 0]]\n #list mapping of vertices to mark vertex visited\n visited = [0 for x in range(len(vertices))]\n \n #number of vertices in the graph\n N = 8\n \n #Driver code\n hamiltonian = Hamiltonian(0)\n hamiltonian.findCycle()\n \n #if the graph doesn't have any Hamiltonian Cycle\n if not hamiltonian.hasCycle:\n print(\"No Hamiltonian Cycle\")<\/pre>\n\n\n\n
- Q.2: What is a Hamiltonian Cycle?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code<\/a><\/li>
- Approach: Backtracking<\/a><\/li>
![\"Graph](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/graph-and-Hamiltonian-Cycle-1024x509.png\")
<\/figure>\n\n\n\n![\"Hamiltonian](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Hamiltonian-Path-1024x624.png\")
<\/figure>\n\n\n\n