# Check if Hamiltonian Cycle exists in a graph using Python

In this blog, we will find whether a graph contains a Hamiltonian cycle or not in Python

### What does one mean by a Hamiltonian path/cycle?

A hamiltonian path refers to a path that passes all the vertices of a graph **exactly once**.

Ex:

A hamiltonian cycle refers to a cycle that passes all the vertices of a graph **exactly once**.

Ex:

### Algorithm:

To find the hamiltonian cycle we will be using backtracking along with DFS to traverse all the different types of hamiltonian paths possible.

- We first create a path list which will store the current path that we have traveled
- Then, we start a DFS from the root and keep appending the different root that we get as we traverse through the graph.
- Parameters we use to see if a node is safe to jump in DFS are:
- If a node does not exist in our already traveled path.
- If we have found a hamiltonian cycle, then we don’t need to traverse any further.

#------------------------------------------ ''' Defining our safe vertex as something which is not in our path ''' def safeVertex(node): if(node in path): return False return True #------------------------------------------- #------------------------------------------- ''' Defining our DFS and Backtracking Logic ''' def cycleDetection(E,n,root): path.append(root) #Seeing all the neigbours of the current root for i in E[root]: #Checking if our vertex satisfies the safe Vertex if(safeVertex(i)): #Checking if a cycle has already been detected or not in the #---------------------previous recursion-------------------- if(cycleDetection(E,n,i)): return True #Checking if our current path has all the vertices if(len(path) == n): #If there is an edge from last vertex to the first vertex in our path #-------------then we have an hamiltonian cycle--------------------- if(path[0] in E[path[len(path)-1]]): return True else: return False #once we are done we remove that particle from the iteration path.pop() #------------------------------------------- #------------------------------------------- ''' Printing True or False based on our output from Cycle Detection ''' def HamiltonianCycle(E,n,root): if(cycleDetection(E,n,root)): print("True") else: print("False") #------------------------------------------- path = [] N_Vertices = int(input()) matrix = list() for i in range(N_Vertices): matrix.append([]) N_Edges = int(input()) for j in range(N_Edges): edge_vertices = input().split() u = int(edge_vertices[0]) v = int(edge_vertices[1]) matrix[u-1].append(v-1) matrix[v-1].append(u-1) HamiltonianCycle(matrix,N_Vertices,0) #This path is actually a Hamiltonian cycle. print(path)

Input: (this is essentially the graph which was given in the hamiltonian cycle example with 7 vertices) 7 10 1 2 1 3 1 6 6 7 7 5 2 3 3 4 3 5 4 5 5 6

Output: True [0, 1, 2, 3, 4, 6, 5]

## Leave a Reply