Scribd
Upload
17 views1 page

Hamiltonian

The document presents a Python function to find Hamiltonian cycles in a given graph using backtracking. It defines helper functions to validate vertices and recursively explore possible paths. If cycles are found, they are printed; otherwise, a message indicates that no cycles exist.

Uploaded by

Arnav Balpande
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
17 views1 page

Hamiltonian

The document presents a Python function to find Hamiltonian cycles in a given graph using backtracking. It defines helper functions to validate vertices and recursively explore possible paths. If cycles are found, they are printed; otherwise, a message indicates that no cycles exist.

Uploaded by

Arnav Balpande
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 1

def hamiltonian_cycle(graph): num_vertices = len(graph) path = [-1] * num_vertices

path[0] = 0
cycles = []
def is_valid_vertex(v, pos, path):
if graph[path[pos - 1]][v] == 0: return False
if v in path: return False
return True
def hamiltonian_cycle_util(pos): if pos == num_vertices:
if graph[path[pos - 1]][path[0]] == 1: cycles.append(path.copy()) return True
else:
return False
for v in range(1, num_vertices): if is_valid_vertex(v, pos, path):
path[pos] = v
if hamiltonian_cycle_util(pos + 1):
path[pos] = -1 # Backtrack return False
hamiltonian_cycle_util(1)
if not cycles:
print("No Hamiltonian cycle exists.") return
print("Hamiltonian cycles:") for cycle in cycles:
for vertex in cycle: print(vertex, end=" ")
print(cycle[0])
graph = [
[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]
] hamiltonian_cycle(graph)

You might also like