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.

  1. /*
  2.  * C++ Program to Find Hamiltonian Cycle
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #define V 5
  8. using namespace std;
  9.  
  10. void printSolution(int path[]);
  11.  
  12. /* 
  13.  * check if the vertex v can be added at index 'pos' in the Hamiltonian Cycle 
  14.  */
  15. bool isSafe(int v, bool graph[V][V], int path[], int pos)
  16. {
  17.     if (graph [path[pos-1]][v] == 0)
  18.         return false;
  19.    for (int i = 0; i < pos; i++)
  20.         if (path[i] == v)
  21.             return false;
  22.     return true;
  23. }
  24.  
  25. /* solve hamiltonian cycle problem */
  26. bool hamCycleUtil(bool graph[V][V], int path[], int pos)
  27. {
  28.     if (pos == V)
  29.     {
  30.         if (graph[ path[pos-1] ][ path[0] ] == 1)
  31.             return true;
  32.         else
  33.             return false;
  34.     }
  35.  
  36.     for (int v = 1; v < V; v++)
  37.     {
  38.         if (isSafe(v, graph, path, pos))
  39.         {
  40.             path[pos] = v;
  41.             if (hamCycleUtil (graph, path, pos+1) == true)
  42.                 return true;
  43.             path[pos] = -1;
  44.         }
  45.     }
  46.     return false;
  47. }
  48.  
  49. /* solves the Hamiltonian Cycle problem using Backtracking.*/
  50. bool hamCycle(bool graph[V][V])
  51. {
  52.     int *path = new int[V];
  53.     for (int i = 0; i < V; i++)
  54.         path[i] = -1;
  55.     path[0] = 0;
  56.     if (hamCycleUtil(graph, path, 1) == false)
  57.     {
  58.         cout<<"\nSolution does not exist"<<endl;
  59.         return false;
  60.     }
  61.     printSolution(path);
  62.     return true;
  63. }
  64.  
  65. /* Main */
  66. void printSolution(int path[])
  67. {
  68.     cout<<"Solution Exists:";
  69.     cout<<" Following is one Hamiltonian Cycle \n"<<endl;
  70.     for (int i = 0; i < V; i++)
  71.         cout<<path[i]<<"  ";
  72.     cout<< path[0]<<endl;
  73. }
  74.  
  75. int main()
  76. {
  77.    /* Let us create the following graph
  78.       (0)--(1)--(2)
  79.        |   / \   |
  80.        |  /   \  |
  81.        | /     \ |
  82.       (3)-------(4)    */
  83.    bool graph1[V][V] = {{0, 1, 0, 1, 0},
  84.                       {1, 0, 1, 1, 1},
  85.                       {0, 1, 0, 0, 1},
  86.                       {1, 1, 0, 0, 1},
  87.                       {0, 1, 1, 1, 0},
  88.                      };
  89.    hamCycle(graph1);
  90.  
  91.    /* Let us create the following graph
  92.       (0)--(1)--(2)
  93.        |   / \   |
  94.        |  /   \  |
  95.        | /     \ |
  96.       (3)       (4)    */
  97.     bool graph2[V][V] = {{0, 1, 0, 1, 0},
  98.                       {1, 0, 1, 1, 1},
  99.                       {0, 1, 0, 0, 1},
  100.                       {1, 1, 0, 0, 0},
  101.                       {0, 1, 1, 0, 0},
  102.                      };
  103.     hamCycle(graph2);
  104.     return 0;
  105. }

advertisement
$ 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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.