Log inSign up
hardGeeksforGeeksNot Started

Hamiltonian Cycle

A Hamiltonian Cycle is a closed loop in a graph that visits every vertex exactly once and returns to the starting vertex. Determine whether a given graph contains a Hamiltonian Cycle and return the path.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given an undirected graph with V vertices numbered 0 to V - 1 and an adjacency matrix or list graph.

A Hamiltonian Cycle is a closed loop that visits every vertex in the graph exactly once and returns to the initial starting vertex.

Determine whether a Hamiltonian Cycle exists in the given graph. If one exists, return an array of vertices representing the cycle starting and ending at vertex 0 (e.g., [0, v1, v2, ..., v_{V-1}, 0]). If no Hamiltonian Cycle exists, return [].

---

### Examples

Example 1: ``text Input: V = 5, 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] ] Output: [0, 1, 2, 4, 3, 0] Explanation: Vertex 0 -> 1 -> 2 -> 4 -> 3 -> 0 visits every vertex {0, 1, 2, 3, 4} exactly once and returns to 0.

Example 2 (No Cycle): ``text Input: V = 5, graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 0, 1], [1, 1, 0, 0, 0], [0, 1, 1, 0, 0] ] Output: [] Explanation: Vertex 3 and vertex 4 are connected only to 0 and 1; no cycle can visit all vertices and return to 0.

---

### Constraints - 1 <= V <= 16 - Undirected graph with no self-loops. - Graph may contain multiple components.

Constraints:

  • 1 <= V <= 16
  • 0-indexed undirected graph

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Contrast Eulerian circuits (polynomial O(V + E)) with Hamiltonian cycles (NP-complete).
  • Apply rotational symmetry to anchor the search at vertex 0.
  • Implement the classic Backtracking search with cycle closure verification.
  • Formulate the Bitmask Dynamic Programming solution for V <= 16.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Traveling Salesperson Problem (TSP) with unweighted edges.
  • Visiting all cities/nodes exactly once and returning to the base.
  • Finding an edge permutation that forms a simple cycle of length V.

Algorithmic Decision Tree:

  • If Eulerian path requested (visit all EDGES once) -> Linear O(V + E) Hierholzer's.
  • If Hamiltonian cycle requested (visit all VERTICES once) -> NP-complete O(V2 * 2V) Bitmask DP or Backtracking.

Connected Patterns:

Travelling Salesman ProblemEulerian Path and CircuitN-Queens

1. All-Permutations Brute Force Generation

Intuition

Generate all (V - 1)! permutations of vertices 1 to V - 1 and verify whether all consecutive pairs and the wrap-around edge exist.

Algorithm

  1. Create array [1, 2, ..., V - 1].
  2. For every permutation of this array:
  3. Form candidate path [0, p1, p2, ..., p_{V-1}, 0].
  4. Check if all V edges exist in the graph.
  5. If valid, return path.
  6. Return [] if no permutation forms a valid cycle.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <algorithm>
5
6using namespace std;
7
8vector<int> hamiltonianCyclePermutations(int V, const vector<vector<int>>& graph) {
9 vector<int> p(V - 1);
10 iota(p.begin(), p.end(), 1);
11
12 do {
13 bool valid = true;
14 int prev = 0;
15 for (int curr : p) {
16 if (!graph[prev][curr]) {
17 valid = false;
18 break;
19 }
20 prev = curr;
21 }
22
23 if (valid && graph[prev][0]) {
24 vector<int> cycle = {0};
25 cycle.insert(cycle.end(), p.begin(), p.end());
26 cycle.push_back(0);
27 return cycle;
28 }
29 } while (next_permutation(p.begin(), p.end()));
30
31 return {};
32}
33
34int main() {
35 int V = 5;
36 vector<vector<int>> graph = {
37 {0, 1, 0, 1, 0},
38 {1, 0, 1, 1, 1},
39 {0, 1, 0, 0, 1},
40 {1, 1, 0, 0, 1},
41 {0, 1, 1, 1, 0}
42 };
43
44 auto cycle = hamiltonianCyclePermutations(V, graph);
45 cout << "Cycle: ";
46 for (int v : cycle) cout << v << " ";
47 cout << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(V! * V)
  • Space complexity: O(V)

2. Backtracking with Neighbor Pruning (Standard DFS)

Intuition

Anchor path at vertex 0. Incrementally try adding unvisited adjacent neighbors. If path reaches length V, check edge back to 0.

Algorithm

  1. Initialize path array of size V, set path[0] = 0.
  2. In solve(pos):
  3. If pos == V:
  4. If edge exists between path[V - 1] and path[0]: return true.
  5. Else: return false.
  6. For each vertex v from 1 to V - 1:
  7. If edge exists between path[pos - 1] and v, AND v is not yet in path:
  8. Set path[pos] = v.
  9. If solve(pos + 1) == true: return true.
  10. Set path[pos] = -1 (backtrack).
  11. Return false.
  12. If solve(1) succeeds, append 0 to path and return it; else return [].

Backtracking Path Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
path[0] = 0
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Try v = 1
Why this step matters

path[0] = 0. Neighbors of 0: 1, 3.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 int V;
8 vector<vector<int>> graph;
9 vector<int> path;
10
11 bool isSafe(int v, int pos) {
12 if (!graph[path[pos - 1]][v]) return false;
13 for (int i = 0; i < pos; ++i) {
14 if (path[i] == v) return false;
15 }
16 return true;
17 }
18
19 bool solve(int pos) {
20 if (pos == V) {
21 return graph[path[pos - 1]][path[0]] == 1;
22 }
23
24 for (int v = 1; v < V; ++v) {
25 if (isSafe(v, pos)) {
26 path[pos] = v;
27 if (solve(pos + 1)) return true;
28 path[pos] = -1; // Backtrack
29 }
30 }
31 return false;
32 }
33
34public:
35 vector<int> findHamiltonianCycle(int v, const vector<vector<int>>& g) {
36 V = v;
37 graph = g;
38 path = vector<int>(V, -1);
39 path[0] = 0;
40
41 if (solve(1)) {
42 vector<int> cycle = path;
43 cycle.push_back(0);
44 return cycle;
45 }
46 return {};
47 }
48};
49
50int main() {
51 int V = 5;
52 vector<vector<int>> graph = {
53 {0, 1, 0, 1, 0},
54 {1, 0, 1, 1, 1},
55 {0, 1, 0, 0, 1},
56 {1, 1, 0, 0, 1},
57 {0, 1, 1, 1, 0}
58 };
59
60 Solution solver;
61 auto cycle = solver.findHamiltonianCycle(V, graph);
62 cout << "Backtracking Cycle: ";
63 for (int v : cycle) cout << v << " ";
64 cout << endl;
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(V!) worst case, heavily pruned on sparse graphs
  • Space complexity: O(V)

3. Held-Karp Bitmask Dynamic Programming

Intuition

Formulate DP state dp[mask][u] where mask denotes the subset of visited vertices and u is the last visited vertex. Achieves optimal O(V2 * 2V) time.

Algorithm

  1. Let dp[mask][u] = true if there exists a simple path starting at 0, visiting exactly the vertices in mask, and ending at u.
  2. Base case: dp[1][0] = true (mask = 1 << 0, ending at 0).
  3. For mask from 1 to (1 << V) - 1:
  4. For u from 0 to V - 1:
  5. If dp[mask][u] is true:
  6. For v from 0 to V - 1:
  7. If (mask & (1 << v)) == 0 and graph[u][v] == 1:
  8. dp[mask | (1 << v)][v] = true.
  9. Check closing edge: for u from 1 to V - 1, if dp[(1 << V) - 1][u] == true and graph[u][0] == 1, cycle exists.
  10. Reconstruct path by backtracking through DP transitions.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6bool hasHamiltonianCycleDP(int V, const vector<vector<int>>& graph) {
7 int totalMask = (1 << V);
8 vector<vector<bool>> dp(totalMask, vector<bool>(V, false));
9 dp[1][0] = true; // Started at 0 with mask (1 << 0)
10
11 for (int mask = 1; mask < totalMask; ++mask) {
12 for (int u = 0; u < V; ++u) {
13 if (!dp[mask][u]) continue;
14
15 for (int v = 0; v < V; ++v) {
16 if (!(mask & (1 << v)) && graph[u][v]) {
17 dp[mask | (1 << v)][v] = true;
18 }
19 }
20 }
21 }
22
23 // Check if full mask has a node connecting back to 0
24 int fullMask = totalMask - 1;
25 for (int u = 1; u < V; ++u) {
26 if (dp[fullMask][u] && graph[u][0]) {
27 return true;
28 }
29 }
30 return false;
31}
32
33int main() {
34 int V = 5;
35 vector<vector<int>> graph = {
36 {0, 1, 0, 1, 0},
37 {1, 0, 1, 1, 1},
38 {0, 1, 0, 0, 1},
39 {1, 1, 0, 0, 1},
40 {0, 1, 1, 1, 0}
41 };
42
43 cout << "Has Hamiltonian Cycle (DP): " << (hasHamiltonianCycleDP(V, graph) ? "true" : "false") << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(V^2 * 2^V)
  • Space complexity: O(V * 2^V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All-Permutations Brute ForceO(V! * V)O(V)Generate all (V - 1)! permutations of vertices 1 to V - 1, then verify all edges in the ring.Testing invalid disconnected sequences.
2.Backtracking with Neighbor Pruning (Standard)O(V!) worst case, heavily pruned in practiceO(V)Anchor at 0. At step pos, only consider unvisited adjacent neighbors of path[pos - 1].Factorial branch exploration.
3.Held-Karp Bitmask Dynamic Programming (Optimal Asymptotic)OptimalO(V^2 * 2^V)O(V * 2^V)Let dp[mask][u] = true if a path exists visiting the subset of vertices in mask ending at u.Memory table size.

Common Pitfalls & Crucial Edge Cases

Forgetting to verify the closing edge back to 0

Successfully finding a path of length V does not guarantee a cycle unless graph[path[V - 1]][0] == 1.

Re-visiting nodes

Failing to check whether the candidate neighbor is already in the current path.

Checking all starting nodes

Wasting time testing start = 1, 2, ..., V - 1 when start = 0 is sufficient.

Crucial Edge Cases to Validate:

  • Complete Graph K_V (V >= 3) — Has (V - 1)! / 2 distinct Hamiltonian cycles.
  • Graph with a vertex of degree 1 (leaf node) — Impossible to form a cycle; immediately returns [].
  • Star graph — No Hamiltonian cycle can exist because leaves cannot be visited without revisiting the center.
  • Line graph — Impossible to close the loop; returns [].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the difference: Eulerian (visits all EDGES once, polynomial) vs Hamiltonian (visits all VERTICES once, NP-complete).
  2. Mention Dirac's Theorem and Ore's Theorem as quick sufficient condition heuristics.
  3. Discuss the reduction to the Traveling Salesperson Problem (TSP).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we fix vertex 0 as the starting node of the Hamiltonian Cycle without loss of generality?

2.What does Dirac's Theorem state regarding the existence of a Hamiltonian Cycle?

Back to DSA Sheet