# 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 ] == 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;`
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<<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. `}`

```\$ 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)

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 