PHP-Fusion Powered Website - Articles: C++ Program to Find Hamiltonian Cycle

Users Online

· Guests Online: 54

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » C++ Program to Find Hamiltonian Cycle

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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

C++ Program to Find Hamiltonian Cycle

C++ Program to Find Hamiltonian Cycle

Comments

Post Comment

Ratings