Program:
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define V 5
void printSolution(int path[]);
bool isSafe(int v, bool graph[V][V], int path[], int pos) {
if (graph[path[pos - 1]][v] == false) {
return false;
}
for (int i = 0; i < pos; i++) {
if (path[i] == v) {
return false;
}
}
return true;
}
bool hamiltonianCycleUtil(bool graph[V][V], int path[], int pos) {
if (pos == V) {
if (graph[path[pos - 1]][path[0]] == true) {
return true;
} else {
return false;
}
}
for (int v = 1; v < V; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamiltonianCycleUtil(graph, path, pos + 1) == true) {
return true;
}
path[pos] = -1;
}
}
return false;
}
bool hamiltonianCycle(bool graph[V][V]) {
int path[V];
for (int i = 0; i < V; i++) {
path[i] = -1;
}
path[0] = 0;
if (hamiltonianCycleUtil(graph, path, 1) == false) {
printf("Solution does not exist");
return false;
}
printSolution(path);
return true;
}
void printSolution(int path[]) {
printf("Hamiltonian Cycle: ");
for (int i = 0; i < V; i++) {
printf("%d ", path[i]);
}
printf("%d", path[0]);
}
int main() {
bool graph[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}
};
clock_t start, end;
double cpu_time_used;
start = clock();
hamiltonianCycle(graph);
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf("\nRunning time: %f seconds\n", cpu_time_used);
return 0;
}
Output:
Hamiltonian Cycle: 0 1 2 4 3 0
Running time: 0.000036 seconds
