C++ Program to Find Hamiltonian Cycle
Posted by Superadmin on August 09 2022 07:11:57

C++ Program to Find Hamiltonian Cycle

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