Introduction

A Hamiltonian cycle in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex. The problem of finding a Hamiltonian cycle is NP-complete, meaning there is no known efficient solution. However, we can implement a backtracking approach to explore possible cycles.

Program Structure

def is_valid(v, pos, path, graph):
    # Check if this vertex can be added to the Hamiltonian Cycle
    if graph[path[pos - 1]][v] == 0:
        return False
    if v in path:
        return False
    return True

def hamiltonian_cycle_util(graph, path, pos):
    # Base case: if all vertices are included in the path
    if pos == len(graph):
        if graph[path[pos - 1]][path[0]] == 1:
            return True
        else:
            return False

    # Try different vertices as the next candidate
    for v in range(1, len(graph)):
        if is_valid(v, pos, path, graph):
            path[pos] = v
            if hamiltonian_cycle_util(graph, path, pos + 1):
                return True
            path[pos] = -1  # Backtrack

    return False

def find_hamiltonian_cycle(graph):
    path = [-1] * len(graph)
    path[0] = 0  # Starting from the first vertex

    if not hamiltonian_cycle_util(graph, path, 1):
        return None
    return path

Code Explanation

• is_valid(v, pos, path, graph): This helper function checks whether the vertex v can be added to the Hamiltonian cycle at position pos. It checks if there is an edge from the last added vertex to v and ensures v has not been visited yet.
• hamiltonian_cycle_util(graph, path, pos): This is a recursive function that attempts to build the Hamiltonian cycle. It checks if the cycle is complete and validates the next vertex to add. If it finds a valid configuration, it returns True; otherwise, it backtracks.
• find_hamiltonian_cycle(graph): This function initializes the path and calls the recursive utility function. It starts the cycle from the first vertex (index 0) and returns the completed path if a Hamiltonian cycle is found.

Usage

To use the program, define a graph as an adjacency matrix. Each element graph[i][j] is 1 if there is an edge between vertex i and vertex j, otherwise it is 0. Call the find_hamiltonian_cycle(graph) function with your graph.

Example

graph = [
    [0, 1, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 1, 0]
]

cycle = find_hamiltonian_cycle(graph)
if cycle:
    print("Hamiltonian Cycle found:", cycle)
else:
    print("No Hamiltonian Cycle found.")

Conclusion

This program demonstrates a backtracking approach to finding a Hamiltonian cycle in a graph. While this method is not efficient for large graphs due to its exponential time complexity, it illustrates the concept of exploring possible solutions recursively.