1. One-Liner
Hamiltonian Cycle builds a simple cycle visiting all vertices once by extending a path with backtracking when no valid next vertex exists.
2. The Problem It Solves
In an undirected graph, does there exist a cycle that visits every vertex exactly once and returns to the starting vertex? This is a classic NP-complete decision problem; exact algorithms for general graphs use exhaustive search with pruning.
3. The Core Idea
Fix a start vertex (often 0). Maintain a path array: at each step, try adding a neighbor that is unvisited and adjacent to the last vertex on the path. When the path length equals N, check an edge back to start. If stuck, remove the last vertex and try another neighbor—pure backtracking on permutations with adjacency constraints.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Init | path[0]=0, remaining -1 |
| 2. Position | Extend from path[pos-1] |
| 3. Candidate | Neighbor v not in path yet |
| 4. Place | path[pos]=v, recurse |
| 5. Complete | If pos==n and edge (last,start) exists, done |
| 6. Backtrack | Clear path[pos] and try next neighbor |
5. Dry Run Example
A 4-cycle square graph: order 0→1→2→3→0 works. Add a chord; multiple Hamiltonian cycles may exist—algorithm finds one or reports none.
6. Key Properties
| Property | Value |
|---|---|
| Decision | NP-complete (general graphs) |
| State | Partial path prefix |
| Pruning | Skip non-adjacent / already used |
7. Where It Is Used
| Domain | Use |
|---|---|
| Theory | Hardness reductions, TSP relationship |
| Operations research | Special cases and heuristics |
| Interviews | Rare full problem; “idea” level often enough |
8. Interview Tips
Don’t claim polynomial exact solver; explain DFS path building, O(N!) flavor, and difference from Eulerian (edges vs vertices). Mention TSP as weighted variant.
9. Comparison with Other Problems
| Problem | Visits |
|---|---|
| Hamiltonian path/cycle | Each vertex once |
| Eulerian circuit | Each edge once |
| TSP | Min-weight Hamiltonian cycle |
10. Complexity
| Metric | Value |
|---|---|
| Time | Exponential in worst case (O(N!)-style) |
| Space | O(N) for path + O(N^2) adjacency matrix storage |
Implementation Example (PYTHON)
def hamiltonian_cycle(graph: list[list[int]]) -> bool:
n = len(graph)
path = [-1] * n
path[0] = 0
def safe(v: int, pos: int) -> bool:
if graph[path[pos - 1]][v] == 0:
return False
return v not in path[:pos]
def hc(pos: int) -> bool:
if pos == n:
return graph[path[pos - 1]][path[0]] == 1
for v in range(1, n):
if safe(v, pos):
path[pos] = v
if hc(pos + 1):
return True
path[pos] = -1
return False
return hc(1)