How to design Hamiltonian Cycle in Python

In this tutorial, we will learn how to design a hamiltonian cycle in Python.

Firstly we will learn what is a hamiltonian cycle.

Hamiltonian Cycle and Graph

Suppose you got a Graph G. Now if you find a cycle containing all the vertices of that Graph, then we can call the cycle a Hamiltonian Cycle.

Now if the Graph is having a hamiltonian cycle then the graph will be known as a hamiltonian graph.

Hamiltonian path:

A path in a connected graph that includes every vertex but not necessarily every edge, then the connected graph is called a hamiltonian path.

Let’s take a simple graph ‘G’ containing 4 vertices and 5 edges represented as G(4,5).
This is the adjacency matrix for the graph:

[[0,1,0,1]
[1,0,1,1]
[0,1,0,1]
[1,1,1,0]]

Note: The adjacency matrix of a graph ‘G’ with ‘n’ vertices is given by a[ij]=1{if there is an edge between i and j vertices} and a[ij]=0 {if there is no edge}

here is the python code.

class Graph():  
    def __init__(self, vertex):  
        self.graph = [[0 for column in range(vertex)]

                            for row in range(vertex)]  
        self.V = vertex
    def isSafe(self, v, pos, hpath):  
        if self.graph[ hpath[pos-1] ][v] == 0:
            return False

        for vertex in hpath:
            if vertex == v:
                return False
        return True

    def hamCycleUtil(self, hpath, pos):
        if pos == self.V:
           
            if self.graph[ hpath[pos-1] ][ hpath[0] ] == 1:
                return True
            else:  
                return False
        for v in range(1,self.V):
            if self.isSafe(v, pos, hpath) == True:
                hpath[pos] = v  

                if self.hamCycleUtil(hpath, pos+1) == True:
                    return True
                hpath[pos] = -1

        return False
    def hamCycle(self):
        hpath= [-1] * self.V  
        hpath[0] = 0
   
        if self.hamCycleUtil(hpath,1) == False:  
   
            print ("No hamiltonian cycle\n")
   
            return False
   
        self.printSolution(hpath)  
   
        return True
   
    def printSolution(self, hpath):
        print ("it is a hamiltonian graph: the possible", " Hamiltonian Cycle is:")
   
        for vertex in hpath:  
   
            print (vertex, end = " ")
   
        print (hpath[0], "\n")

g1 = Graph(4)  

g1.graph = [ [0, 1,0,1], [1,0,1,1],  

            [0,1,0,1],[1,1,1,0],]  

g1.hamCycle();  

g2 = Graph(4)  

g2.graph = [ [0,1,0,0], [1,0,0,1],  

        [0,0,0,1], [0,1,1,0],]  

g2.hamCycle();

 it is a hamiltonian graph: the possible Hamiltonian Cycle is:
0 1 2 3 0
No hamiltonian cycle

Finally, the applications of the Hamiltonian cycle are it is used in computer graphics and circuit designs.
also, read rfind method in python