DAA (Unit-5)
Solving problems using
Backtracking
Hamiltonian Cycle problem
By
Dr. Ratnesh Litoriya
Medi-Caps University, Indore (M.P.)
5/6/2023
Backtracking
Backtracking is a technique used to solve
problems with a large search space, by
systematically trying and eliminating
possibilities.
It uses recursive calling to find the solution
by building a solution step by step increasing
values with time. It removes the solutions that
doesn't give rise to the solution of the
problem based on the constraints given to
solve the problem.
2
Hamiltonian Circuit Problem
Hamiltonian Circuit – a simple cycle
including all the vertices of the graph
This is NP Hard problem
Hamiltonian Cycle
Hamiltonian Path in an undirected graph is a path
that visits each vertex exactly once.
A Hamiltonian cycle (or Hamiltonian circuit) is a
Hamiltonian Path such that there is an edge (in the
graph) from the last vertex to the first vertex of the
Hamiltonian Path.
Determine whether a given graph contains
Hamiltonian Cycle or not. If it contains, then prints
the path.
Hamiltonian Cycle
Consider a graph G = (V, E), we have to find a Hamiltonian
circuit using Backtracking method.
Hamiltonian Cycle
Firstly, we start our search with vertex 'a.' this vertex 'a'
becomes the root of our implicit tree.
Hamiltonian Cycle
Next, we choose vertex 'b' adjacent to 'a' as it comes first in
lexicographical order (b, c, d).
Hamiltonian Cycle
Next, we select 'c' adjacent to 'b.'
Hamiltonian Cycle
Next, we select 'd' adjacent to 'c.'
Hamiltonian Cycle
Next, we select 'e' adjacent to 'd.'
Hamiltonian Cycle
Next, we select vertex 'f'
adjacent to 'e.' The vertex
adjacent to 'f' is d and e, but they
have already visited. Thus, we
get the dead end, and we
backtrack one step and remove
the vertex 'f' from partial solution.
Hamiltonian Cycle
From backtracking, the vertex
adjacent to 'e' is b, c, d, and f from
which vertex 'f' has already been
checked, and b, c, d have already
visited. So, again we backtrack one
step. Now, the vertex adjacent to d
are e, f from which e has already been
checked, and adjacent of 'f' are d and
e. If 'e' vertex, revisited them we get a
dead state. So again we backtrack
one step.
Hamiltonian Cycle
Now, adjacent to c is 'e' and
adjacent to 'e' is 'f' and
adjacent to 'f' is 'd' and
adjacent to 'd' is 'a.'
Hamiltonian Cycle
Here, we get the Hamiltonian
Cycle as all the vertex other than
the start vertex 'a' is visited only
once. (a - b - c - e - f -d - a).
Here we have generated one
Hamiltonian circuit, but another
Hamiltonian circuit can also be
obtained by considering another vertex
Hamiltonian Cycle
While generating the state space tree following bounding
functions are to be considered, which are as follows:
The ith vertex in the path must be adjacent to the (i-
1)th vertex in any path.
The starting vertex and the (n-1)th vertex should be
adjacent.
The ith vertex cannot be one of the first (i-1)th vertex in the
path.
Hamiltonian Cycle (Algorithm)
Hamiltonian Cycle
Complexity analysis
