# 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