Objective

The objective of this program is to determine if a given undirected graph contains a Hamiltonian cycle.
A Hamiltonian cycle is a cycle that visits each vertex exactly once and returns to the starting vertex.
This problem is NP-complete, meaning there is no known efficient algorithm to solve it for all cases.

C Code Implementation

#include 
#include 

#define V 5 // Number of vertices in the graph

// Function to check if the vertex can be added to the path
int isSafe(int v, int graph[V][V], int path[], int pos) {
    // Check if this vertex is an adjacent vertex of the previously added vertex
    if (graph[path[pos - 1]][v] == 0) return 0;

    // Check if the vertex has already been included
    for (int i = 0; i < pos; i++)
        if (path[i] == v) return 0;

    return 1;
}

// Utility function to solve the Hamiltonian Cycle problem
int hamiltonianCycleUtil(int graph[V][V], int path[], int pos) {
    // Base case: if all vertices are included in the path
    if (pos == V) {
        // And if there is an edge from the last included vertex to the first vertex
        return (graph[path[pos - 1]][path[0]] == 1);
    }

    // Try different vertices as the next candidate in the Hamiltonian Cycle
    for (int v = 1; v < V; v++) {
        if (isSafe(v, graph, path, pos)) {
            path[pos] = v;

            // Recursion to construct the rest of the path
            if (hamiltonianCycleUtil(graph, path, pos + 1)) return 1;

            // If adding vertex v doesn't lead to a solution, remove it
            path[pos] = -1;
        }
    }
    return 0;
}

// Function to solve the Hamiltonian Cycle problem
int hamiltonianCycle(int graph[V][V]) {
    int *path = malloc(V * sizeof(int));
    for (int i = 0; i < V; i++) path[i] = -1;

    // Let the first vertex in the path be the first vertex
    path[0] = 0;

    // Call the utility function to solve the problem
    if (hamiltonianCycleUtil(graph, path, 1) == 0) {
        printf("Solution does not exist\n");
        return 0;
    }

    printSolution(path);
    free(path);
    return 1;
}

// Function to print the solution
void printSolution(int path[]) {
    printf("Hamiltonian Cycle exists: ");
    for (int i = 0; i < V; i++)
        printf("%d ", path[i]);
    printf("%d\n", path[0]); // to show the cycle
}

// Main function
int main() {
    // Example graph
    int graph[V][V] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 1, 1},
        {1, 0, 1, 0, 1},
        {0, 1, 1, 1, 0}
    };

    hamiltonianCycle(graph);
    return 0;
}

Program Structure

• isSafe Function: Checks if a vertex can be added to the current path without violating the Hamiltonian cycle constraints.
• hamiltonianCycleUtil Function: Recursively attempts to construct the Hamiltonian cycle using backtracking.
• hamiltonianCycle Function: Initializes the path and starts the process to find the Hamiltonian cycle.
• printSolution Function: Outputs the Hamiltonian cycle found (if exists).
• main Function: Sets up the graph and calls the function to find the Hamiltonian cycle.

How to Run the Program

1. 1. Copy the code into a text editor and save it as hamiltonian_cycle.c.
   2. Open a terminal (command prompt) and navigate to the directory where the file is saved.
   3. Compile the program using the following command:

gcc hamiltonian_cycle.c -o hamiltonian_cycle

1. 1. Run the compiled program:

./hamiltonian_cycle

The output will indicate whether a Hamiltonian cycle exists and, if so, it will display the cycle.