Hamiltonian Cycle is solved by backtracking: build a path one vertex at a time, ensuring each candidate vertex is adjacent to the previous one and not reused. A valid solution has n vertices and an edge back to the start.
bool isSafe(int v, vector<vector<int>>& g, vector<int>& path, int pos) {
if (!g[path[pos - 1]][v]) return false;
for (int i = 0; i < pos; i++) if (path[i] == v) return false;
return true;
}
bool solve(vector<vector<int>>& g, vector<int>& path, int pos) {
int n = g.size();
if (pos == n) return g[path[pos - 1]][path[0]] == 1;
for (int v = 1; v < n; v++) {
if (isSafe(v, g, path, pos)) {
path[pos] = v;
if (solve(g, path, pos + 1)) return true;
path[pos] = -1;
}
}
return false;
}Add one valid unvisited adjacent vertex at each recursion level.
Reject candidates that are non-adjacent or already used.
Worst-case exhaustive search is factorial.
Quiz coming soon for this algorithm.