# C Program to Find Hamiltonian Cycle in an UnWeighted Graph

This is a C Program to find hamilton cycle. Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path. Determine whether a given graph contains Hamiltonian Cycle or not. If it contains, then print the path. Following are the input and output of the required function.

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

1. `#include<stdio.h>`
2. `#include<stdlib.h>`
3. ` `
4. `// Number of vertices in the graph`
5. `#define V 5`
6. ` `
7. `void printSolution(int path[]);`
8. ` `
9. `/* A utility function to check if the vertex v can be added at index 'pos'`
10. ` in the Hamiltonian Cycle constructed so far (stored in 'path[]') */`
11. `int isSafe(int v, int graph[V][V], int path[], int pos) {`
12. `    /* Check if this vertex is an adjacent vertex of the previously`
13. `     added vertex. */`
14. `    if (graph[path[pos - 1]][v] == 0)`
15. `        return 0;`
16. ` `
17. `    /* Check if the vertex has already been included.`
18. `     This step can be optimized by creating an array of size V */`
19. `    int i;`
20. `    for (i = 0; i < pos; i++)`
21. `        if (path[i] == v)`
22. `            return 0;`
23. ` `
24. `    return 1;`
25. `}`
26. ` `
27. `/* A recursive utility function to solve hamiltonian cycle problem */`
28. `int hamCycleUtil(int graph[V][V], int path[], int pos) {`
29. `    /* base case: If all vertices are included in Hamiltonian Cycle */`
30. `    if (pos == V) {`
31. `        // And if there is an edge from the last included vertex to the`
32. `        // first vertex`
33. `        if (graph[path[pos - 1]][path[0]] == 1)`
34. `            return 1;`
35. `        else`
36. `            return 0;`
37. `    }`
38. ` `
39. `    // Try different vertices as a next candidate in Hamiltonian Cycle.`
40. `    // We don't try for 0 as we included 0 as starting point in in hamCycle()`
41. `    int v;`
42. `    for (v = 1; v < V; v++) {`
43. `        /* Check if this vertex can be added to Hamiltonian Cycle */`
44. `        if (isSafe(v, graph, path, pos)) {`
45. `            path[pos] = v;`
46. ` `
47. `            /* recur to construct rest of the path */`
48. `            if (hamCycleUtil(graph, path, pos + 1) == 1)`
49. `                return 1;`
50. ` `
51. `            /* If adding vertex v doesn't lead to a solution,`
52. `             then remove it */`
53. `            path[pos] = -1;`
54. `        }`
55. `    }`
56. ` `
57. `    /* If no vertex can be added to Hamiltonian Cycle constructed so far,`
58. `     then return 0 */`
59. `    return 0;`
60. `}`
61. ` `
62. `/* This function solves the Hamiltonian Cycle problem using Backtracking.`
63. ` It mainly uses hamCycleUtil() to solve the problem. It returns 0`
64. ` if there is no Hamiltonian Cycle possible, otherwise return 1 and`
65. ` prints the path. Please note that there may be more than one solutions,`
66. ` this function prints one of the feasible solutions. */`
67. `int hamCycle(int graph[V][V]) {`
68. `    int *path = new int[V];`
69. `    int i;`
70. `    for (i = 0; i < V; i++)`
71. `        path[i] = -1;`
72. ` `
73. `    /* Let us put vertex 0 as the first vertex in the path. If there is`
74. `     a Hamiltonian Cycle, then the path can be started from any point`
75. `     of the cycle as the graph is undirected */`
76. `    path[0] = 0;`
77. `    if (hamCycleUtil(graph, path, 1) == 0) {`
78. `        printf("\nSolution does not exist");`
79. `        return 0;`
80. `    }`
81. ` `
82. `    printSolution(path);`
83. `    return 1;`
84. `}`
85. ` `
86. `/* A utility function to print solution */`
87. `void printSolution(int path[]) {`
88. `    printf("Solution Exists:"`
89. `        " Following is one Hamiltonian Cycle \n");`
90. `    int i;`
91. `    for (i = 0; i < V; i++)`
92. `        printf(" %d ", path[i]);`
93. ` `
94. `    // Let us print the first vertex again to show the complete cycle`
95. `    printf(" %d ", path[0]);`
96. `    printf("\n");`
97. `}`
98. ` `
99. `// driver program to test above function`
100. `int main() {`
101. `    /* Let us create the following graph`
102. `     (0)--(1)--(2)`
103. `     |   / \   |`
104. `     |  /   \  |`
105. `     | /     \ |`
106. `     (3)-------(4)    */`
107. `    int graph1[V][V] = { { 0, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1 },`
108. `            { 0, 1, 0, 0, 1 }, { 1, 1, 0, 0, 1 }, { 0, 1, 1, 1, 0 }, };`
109. ` `
110. `    // Print the solution`
111. `    hamCycle(graph1);`
112. ` `
113. `    /* Let us create the following graph`
114. `     (0)--(1)--(2)`
115. `     |   / \   |`
116. `     |  /   \  |`
117. `     | /     \ |`
118. `     (3)       (4)    */`
119. `    int graph2[V][V] = { { 0, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1 },`
120. `            { 0, 1, 0, 0, 1 }, { 1, 1, 0, 0, 0 }, { 0, 1, 1, 0, 0 }, };`
121. ` `
122. `    // Print the solution`
123. `    hamCycle(graph2);`
124. ` `
125. `    return 0;`
126. `}`

Output:

```\$ gcc HamiltonCycle.c
\$ ./a.out

Solution Exists: Following is one Hamiltonian Cycle
0  1  2  4  3  0

Solution does not exist```

Sanfoundry Global Education & Learning Series – 1000 C Programs.