Hamiltonian Cycle

Find a cycle that visits every vertex exactly once and returns to the start. Extend the current path to an unvisited neighbour; when all vertices are used, check the last vertex connects back to the first.

Category

Backtracking

Time complexity

O(n!)

Space complexity

O(n)

Pseudocode

path = [start]
extend to any unvisited neighbour
all vertices used + edge back to start ⇒ cycle
stuck ⇒ backtrack

Reference implementation

def solve(path):
    if len(path) == n:
        return path[-1] in adj[path[0]]
    for v in adj[path[-1]]:
        if v not in path and solve(path+[v]): return True
    return False

Open the interactive Hamiltonian Cycle visualisation →