This C++ Program demonstrates the implementation of Hamiltonian Cycle.

Here is source code of the C++ Program to Find Hamiltonian Cycle in a Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C++ Program to Find Hamiltonian Cycle`

`*/`

`#include <iostream>`

`#include <cstdio>`

`#include <cstdlib>`

`#define V 5`

using namespace std;

void printSolution(int path[]);

`/*`

`* check if the vertex v can be added at index 'pos' in the Hamiltonian Cycle`

`*/`

bool isSafe(int v, bool graph[V][V], int path[], int pos)

`{`

if (graph [path[pos-1]][v] == 0)

return false;

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

if (path[i] == v)

return false;

return true;

`}`

`/* solve hamiltonian cycle problem */`

bool hamCycleUtil(bool graph[V][V], int path[], int pos)

`{`

if (pos == V)

`{`

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

return true;

`else`

return false;

`}`

for (int v = 1; v < V; v++)

`{`

if (isSafe(v, graph, path, pos))

`{`

path[pos] = v;

if (hamCycleUtil (graph, path, pos+1) == true)

return true;

path[pos] = -1;

`}`

`}`

return false;

`}`

`/* solves the Hamiltonian Cycle problem using Backtracking.*/`

bool hamCycle(bool graph[V][V])

`{`

int *path = new int[V];

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

path[i] = -1;

path[0] = 0;

if (hamCycleUtil(graph, path, 1) == false)

`{`

cout<<"\nSolution does not exist"<<endl;

return false;

`}`

printSolution(path);

return true;

`}`

`/* Main */`

void printSolution(int path[])

`{`

cout<<"Solution Exists:";

cout<<" Following is one Hamiltonian Cycle \n"<<endl;

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

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

cout<< path[0]<<endl;

`}`

int main()

`{`

`/* Let us create the following graph`

`(0)--(1)--(2)`

`| / \ |`

`| / \ |`

`| / \ |`

`(3)-------(4) */`

bool graph1[V][V] = {{0, 1, 0, 1, 0},

{1, 0, 1, 1, 1},

{0, 1, 0, 0, 1},

{1, 1, 0, 0, 1},

{0, 1, 1, 1, 0},

};

hamCycle(graph1);

`/* Let us create the following graph`

`(0)--(1)--(2)`

`| / \ |`

`| / \ |`

`| / \ |`

`(3) (4) */`

bool graph2[V][V] = {{0, 1, 0, 1, 0},

{1, 0, 1, 1, 1},

{0, 1, 0, 0, 1},

{1, 1, 0, 0, 0},

{0, 1, 1, 0, 0},

};

hamCycle(graph2);

return 0;

`}`

$ g++ hamiltonian.cpp $ a.out Solution Exists: Following is one Hamiltonian Cycle 0 1 2 4 3 0 Solution does not exist ------------------ (program exited with code: 1) Press return to continue

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

If you wish to look at all C++ Programming examples, go to C++ Programs.