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]