[go: up one dir, main page]
Scribd
Upload
12 views8 pages

Daa PR09 123

Uploaded by

gilfoylesatanist
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views8 pages

Daa PR09 123

Uploaded by

gilfoylesatanist
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Bharati Vidyapeeth (Deemed To Be University)

College of Engineering, Pune

DEPARTMENT OF COMPUTER ENGINEERING

Design and Analysis Algorithm

PRACTICAL NO- 09

NAME: Sashank Yadav


PRN NO: 1814110120
ROLL NO: 123
CLASS: B.Tech SEM 6 DIV 2
Aim: Backtracking II: Implement Hamiltonian Cycle.

Objective: To learn backtracking with the help of Hamiltonian cycle

Theory:
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 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 print the path. Following are the input and output of the
required function.
Input:
A 2D array graph[V][V] where V is the number of vertices in graph and
graph[V][V] is adjacency matrix representation of the graph. A value graph[i][j]
is 1 if there is a direct edge from i to j, otherwise graph[i][j] is 0.
Output:
An array path[V] that should contain the Hamiltonian Path. path[i] should
represent the ith vertex in the Hamiltonian Path. The code should also return
false if there is no Hamiltonian Cycle in the graph.

And the following graph doesn’t contain any Hamiltonian Cycle


History:
The Hamiltonian cycle was named after Sir William Rowan Hamilton who, in
1857, invented a puzzle-game which involved hunting for a Hamiltonian
cycle. The game, called the Icosian game, was distributed as a
dodecahedron graph with a hole at each vertex. To solve the puzzle or win
the game one had to use pegs and string to find the Hamiltonian cycle — a
closed loop that visited every hole exactly once.
Every complete graph with more than two vertices is a Hamiltonian graph. This
follows from the definition of a complete graph: an undirected, simple graph
such that every pair of nodes is connected by a unique edge.

The graph of every platonic solid is a Hamiltonian graph. So the graph of a


cube, a tetrahedron, an octahedron, or an icosahedron are all Hamiltonian
graphs with Hamiltonian cycles.
A graph with n vertices (where n > 3) is Hamiltonian if the sum of the degrees
of every pair of non-adjacent vertices is n or greater. This is known as Ore’s
theorem.

Applications of Hamiltonian cycles


and Graphs
A search for Hamiltonian cycles isn’t just a fun game for the afternoon
off. It has real applications in such diverse fields as computer graphics,
electronic circuit design, mapping genomes, and operations research.

For instance, when mapping genomes scientists must combine many tiny
fragments of genetic code (“reads”, they are called), into one single genomic
sequence (a ‘superstring’). This can be done by finding a Hamiltonian cycle or
Hamiltonian path, where each of the reads are considered nodes in a graph and
each overlap (place where the end of one read matches the beginning of
another) is considered to be an edge.

In a much less complex application of exactly the same math, school districts
use Hamiltonian cycles to plan the best route to pick up students from across
the district. Here students may be considered nodes, the paths between them
edges, and the bus wishes to travel a route that will pass each students house
exactly once.
Backtracking Algorithm for Hamiltonian cycle
Step1 : Create an empty path array and add vertex 0 to it.

Step 2: Add other vertices, starting from the vertex 1.

Step 3: Before adding a vertex, check for whether it is adjacent to the previously
added vertex and not already added. If we find such a vertex, we add the vertex
as part of the solution.

Step 4: If we do not find a vertex then we return false.

Analysis :
Time complexity of the above algorithm is O(2nn2).

Code:
#include<iostream>

#define NODE 4

using namespace std;

int graph[NODE][NODE];

int path[NODE];

void displayCycle() { //Function to display the cycle obtained

cout<<"The Hamilton Cycle : " << endl;

for (int i = 0; i < NODE; i++)

cout << path[i] << " ";

cout << path[0] << endl; //print the first vertex again

}
bool isValid(int v, int k) {

if (graph [path[k-1]][v] == 0) //if there is no edge

return false;

for (int i = 0; i < k; i++) //if vertex is already taken, skip that

if (path[i] == v)

return false;

return true;

bool cycleFound(int k) {

if (k == NODE) { //when all vertices are in the path

if (graph[path[k-1]][ path[0] ] == 1 )

return true;

else

return false;

for (int v = 1; v < NODE; v++) { //for all vertices except starting point

if (isValid(v,k)) { //if possible to add v in the path

path[k] = v;

if (cycleFound (k+1) == true)

return true;

path[k] = -1; //when k vertex will not in the solution

}
return false;

bool hamiltonianCycle() {

for (int i = 0; i < NODE; i++)

path[i] = -1;

path[0] = 0; //first vertex as 0

if ( cycleFound(1) == false ) {

cout << "Solution does not exist"<<endl;

return false;

displayCycle();

return true;

int main() {

int i,j;

cout << "Enter the Graph : " << endl;

for (i=0;i<NODE;i++){

for (j=0;j<NODE;j++){

cout << "Graph G(" << (i+1) << "," << (j+1) << ") = ";

cin >> graph[i][j];

cout << endl;


cout << "The Graph :" << endl;

for (i=0;i<NODE;i++){

for (j=0;j<NODE;j++){

cout << graph [i][j] << "\t";

cout << endl;

cout << endl;

hamiltonianCycle();

Output:
Conclusion :
In this practical we studied about Hamiltonian Cycle and implemented
Hamiltonian Cycle in C++ using Backtracking II

You might also like