Program Explanation

A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex. The following C++ program uses backtracking to find a Hamiltonian cycle in a given graph.

Program Structure

• Graph Representation: The graph is represented using an adjacency matrix.
• Backtracking Function: The function hamiltonianCycleUtil recursively tries to build the Hamiltonian cycle.
• Main Function: The function hamiltonianCycle initializes necessary data and calls the backtracking function.

Code

#include <iostream> 
#include <vector> 
#include <string>

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

using namespace std;

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

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

    return true;
}

// Utility function to solve the Hamiltonian cycle problem
bool hamiltonianCycleUtil(vector<vector>& graph, vector& 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, path, pos, graph)) {
            path[pos] = v;

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

            // Backtrack
            path[pos] = -1;
        }
    }
    return false;
}

// Function to solve the Hamiltonian Cycle problem
bool hamiltonianCycle(vector<vector>& graph) {
    vector path(V, -1);
    path[0] = 0; // Starting from the first vertex

    if (!hamiltonianCycleUtil(graph, path, 1)) {
        cout << "Solution does not exist";
        return false;
    }

    printSolution(path);
    return true;
}

// Function to print the solution
void printSolution(vector& path) {
    cout << "Hamiltonian Cycle exists: ";
    for (int i = 0; i < V; i++)
        cout << path[i] << " ";
    cout << path[0]; // Print the starting vertex again
}

// Driver code
int main() {
    // Example graph represented as an adjacency matrix
    vector<vector> graph = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 1, 0},
        {0, 1, 0, 0, 1},
        {1, 1, 0, 0, 1},
        {0, 0, 1, 1, 0}
    };

    hamiltonianCycle(graph);
    return 0;
}

Documentation

• isSafe: Checks if the next vertex can be added to the Hamiltonian path.
• hamiltonianCycleUtil: Recursive utility function to find the Hamiltonian cycle.
• hamiltonianCycle: Initializes the path and starts the cycle finding process.
• printSolution: Prints the found Hamiltonian cycle.

Conclusion

This C++ program effectively finds a Hamiltonian cycle using backtracking. While this approach works well for small graphs, it may not be efficient for larger graphs due to its exponential time complexity.