Day 51: Hamiltonian Cycle

Table of Contents

Day 51: Hamiltonian Cycle #

Welcome to Day 51 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Hamiltonian Cycle problem, a classic problem in graph theory that demonstrates the power and limitations of backtracking algorithms.

What is a Hamiltonian Cycle? #

A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph that visits each vertex exactly once and returns to the starting vertex. It’s named after the mathematician William Rowan Hamilton.

Understanding the Problem #

  • We have an undirected graph G = (V, E), where V is the set of vertices and E is the set of edges.
  • We need to find a cycle that visits every vertex exactly once and returns to the starting vertex.
  • If such a cycle exists, the graph is called Hamiltonian.

Backtracking Approach #

We’ll use a backtracking approach to solve this problem:

  1. Start from a vertex (typically vertex 0).
  2. Add the current vertex to the path.
  3. If all vertices are visited and there’s an edge from the last vertex to the first vertex, we’ve found a Hamiltonian cycle.
  4. Otherwise, try adding each adjacent unvisited vertex to the path.
  5. If adding a vertex doesn’t lead to a solution, backtrack (remove it from the path) and try the next vertex.
  6. If all vertices have been tried and no solution is found, return false.

Implementation #

Here’s a Python implementation of the Hamiltonian Cycle problem:

def hamiltonian_cycle(graph):
    V = len(graph)
    path = [0] * V
    path[0] = 0  # Start from vertex 0
    
    if not hamiltonian_util(graph, path, 1):
        print("No Hamiltonian Cycle exists")
        return False
    
    print_solution(path)
    return True

def hamiltonian_util(graph, path, pos):
    if pos == len(graph):
        # Check if there is an edge from the last vertex to the first vertex
        if graph[path[pos-1]][path[0]] == 1:
            return True
        else:
            return False
    
    for v in range(1, len(graph)):
        if is_safe(v, graph, path, pos):
            path[pos] = v
            
            if hamiltonian_util(graph, path, pos+1):
                return True
            
            # Backtrack
            path[pos] = -1
    
    return False

def is_safe(v, graph, path, pos):
    # Check if this vertex is adjacent to the previously added vertex
    if graph[path[pos-1]][v] == 0:
        return False
    
    # Check if the vertex has already been included in the path
    if v in path:
        return False
    
    return True

def print_solution(path):
    print("Hamiltonian Cycle found:")
    for vertex in path:
        print(vertex, end=" ")
    print(path[0])  # Print the first vertex again to complete the cycle

# Example usage
graph = [
    [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]
]

hamiltonian_cycle(graph)

Time Complexity #

The time complexity of this algorithm is O(N!), where N is the number of vertices in the graph. This is because, in the worst case, we might need to explore all possible permutations of vertices.

Space Complexity #

The space complexity is O(N) to store the path and for the recursion stack.

Optimizations #

  1. Pruning: Implement additional checks to prune the search space early.
  2. Heuristics: Use heuristics to guide the search towards more promising paths first.
  3. Iterative Deepening: Start with shorter paths and gradually increase the path length.

Variations of the Problem #

  1. Hamiltonian Path: Find a path that visits each vertex exactly once (doesn’t need to return to the start).
  2. Traveling Salesman Problem: Find the shortest Hamiltonian cycle in a weighted graph.
  3. Knight’s Tour: A specific application of the Hamiltonian cycle problem on a chessboard.

Real-world Applications #

  1. Circuit design in electronics
  2. Route planning and logistics
  3. DNA fragment assembly in bioinformatics
  4. Network design and optimization

Exercise #

  1. Modify the solution to find all possible Hamiltonian cycles in a graph.
  2. Implement an iterative (non-recursive) solution to the Hamiltonian cycle problem.
  3. Solve the Knight’s Tour problem on a standard 8x8 chessboard using the concepts learned today.

Summary #

Today, we explored the Hamiltonian Cycle problem, a classic graph theory problem that demonstrates the power and limitations of backtracking algorithms. We implemented a solution, discussed its time and space complexity, and looked at possible optimizations and variations of the problem.

The Hamiltonian Cycle problem is NP-complete, which means there’s no known polynomial-time algorithm to solve it for all cases. However, understanding and implementing this algorithm provides valuable insights into graph theory and backtracking techniques.

Tomorrow, we’ll dive into another interesting graph problem: Graph Coloring. Stay tuned!