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:

 1def hamiltonian_cycle(graph):
 2    V = len(graph)
 3    path = [0] * V
 4    path[0] = 0  # Start from vertex 0
 5    
 6    if not hamiltonian_util(graph, path, 1):
 7        print("No Hamiltonian Cycle exists")
 8        return False
 9    
10    print_solution(path)
11    return True
12
13def hamiltonian_util(graph, path, pos):
14    if pos == len(graph):
15        # Check if there is an edge from the last vertex to the first vertex
16        if graph[path[pos-1]][path[0]] == 1:
17            return True
18        else:
19            return False
20    
21    for v in range(1, len(graph)):
22        if is_safe(v, graph, path, pos):
23            path[pos] = v
24            
25            if hamiltonian_util(graph, path, pos+1):
26                return True
27            
28            # Backtrack
29            path[pos] = -1
30    
31    return False
32
33def is_safe(v, graph, path, pos):
34    # Check if this vertex is adjacent to the previously added vertex
35    if graph[path[pos-1]][v] == 0:
36        return False
37    
38    # Check if the vertex has already been included in the path
39    if v in path:
40        return False
41    
42    return True
43
44def print_solution(path):
45    print("Hamiltonian Cycle found:")
46    for vertex in path:
47        print(vertex, end=" ")
48    print(path[0])  # Print the first vertex again to complete the cycle
49
50# Example usage
51graph = [
52    [0, 1, 0, 1, 0],
53    [1, 0, 1, 1, 1],
54    [0, 1, 0, 0, 1],
55    [1, 1, 0, 0, 1],
56    [0, 1, 1, 1, 0]
57]
58
59hamiltonian_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!

Solution#

 1# Exercise 1: Find ALL Hamiltonian cycles in an undirected graph.
 2# We fix vertex 0 as the start to avoid printing rotations of the same cycle.
 3def all_hamiltonian_cycles(graph):
 4    n = len(graph)
 5    cycles = []
 6    path = [0]
 7    visited = [False] * n
 8    visited[0] = True
 9
10    def backtrack():
11        if len(path) == n:
12            # All vertices used; a cycle needs an edge back to the start.
13            if graph[path[-1]][0] == 1:
14                cycles.append(path + [0])
15            return
16        for v in range(1, n):
17            if not visited[v] and graph[path[-1]][v] == 1:
18                visited[v] = True
19                path.append(v)
20                backtrack()
21                path.pop()          # Backtrack.
22                visited[v] = False
23
24    backtrack()
25    return cycles
26
27graph = [
28    [0, 1, 0, 1, 0],
29    [1, 0, 1, 1, 1],
30    [0, 1, 0, 0, 1],
31    [1, 1, 0, 0, 1],
32    [0, 1, 1, 1, 0],
33]
34for cycle in all_hamiltonian_cycles(graph):
35    print(" -> ".join(map(str, cycle)))