A Hamiltonian path visits every vertex of a graph exactly once, moving only along real edges. A Hamiltonian cycle is the same walk with one extra demand: the last vertex must also connect back to the first, closing the walk into a loop. Both are easy to confuse with the similarly-named Eulerian path/circuit — visiting every edge exactly once — Hamiltonian problems are about covering every vertex, and edges are just the moves you're allowed to make between them. Like N-Queens, Sudoku, and Graph Coloring, there's no formula and no greedy rule that always finds one — the same backtracking discipline applies: extend the walk with an unvisited neighbor, and the instant nowhere further is reachable, undo the last step and try a different neighbor. The famous Traveling Salesman Problem builds directly on this: TSP asks for the cheapest Hamiltonian cycle in a weighted graph, an optimization question, while this page asks the simpler yes/no question first — does a Hamiltonian cycle exist at all. The site's Held–Karp Algorithm entry answers that harder optimization question, by dynamic programming rather than backtracking.
The graph below has 6 vertices and 9 edges. Pick a goal — Hamiltonian path (visit every vertex once, any endpoints) or Hamiltonian cycle (same, but the last vertex must also connect back to A) — then press Step or Run. The walk always starts at A. At each step the search extends the current walk to the next unvisited neighbor of the current vertex, trying neighbors in alphabetical order; a vertex already on the walk is simply skipped, not tried. Each newly visited vertex is labeled with its position in the walk (for example "C·2"), and the edge just taken is highlighted. When all 6 vertices are on the walk, cycle mode makes one more check — does the last vertex connect back to A? — and backtracks exactly like any other dead end if it doesn't.
The search never revisits a vertex — each recursive call only considers neighbors that aren't already on the walk — so it never has to detect a repeat after the fact, the walk is a simple path by construction at every step. That's also exactly why the two goals cost different amounts of work on the identical graph: a Hamiltonian path only has to reach length 6, so the very first walk that manages to touch all 6 vertices ends the search immediately. A Hamiltonian cycle has to reach length 6 and have its last vertex adjacent to A — the demo's own measured counts make the gap concrete: path mode finds A·C·D·F·B·E in 14 attempts and 9 backtracks, while cycle mode, started fresh on the same graph with the same alphabetical neighbor order, has to reject that same length-6 walk (E isn't adjacent to A) and keep searching, eventually finding A·C·E·B·F·D — which does close back to A — in 20 attempts and 15 backtracks. Same graph, same starting vertex, same neighbor order, a strictly harder question costs strictly more search.
function hamiltonianWalk(adjacency, start, requireCycle) {
const n = adjacency.length;
const visited = new Array(n).fill(false);
const path = [start];
visited[start] = true;
function extend() {
if (path.length === n) {
if (!requireCycle) return true;
const last = path[path.length - 1];
return adjacency[last].includes(start); // does it close back to start?
}
const current = path[path.length - 1];
for (const next of adjacency[current]) {
if (visited[next]) continue; // already on the walk — skip, don't count as a try
visited[next] = true;
path.push(next);
if (extend()) return true;
path.pop(); // backtrack: undo, try the next neighbor
visited[next] = false;
}
return false;
}
return extend() ? path.slice() : null;
}A path doesn't imply a cycle — check which one you actually need. This demo's own default graph makes the gap concrete rather than just asserting it: run it in path mode and the search happily reports success with F as the final vertex — F has no edge back to A, so that exact same walk is not a Hamiltonian cycle. Switch the goal selector to cycle mode on the identical graph and the search correctly keeps going past that point, discards the F-ending walk, and finds a different one that does close the loop. Code written for "does a Hamiltonian path exist" silently gives a wrong answer to "does a Hamiltonian cycle exist" if the closing-edge check is left out — the two are genuinely different questions, not a stricter/looser version of the same one where skipping the check is merely conservative.
Neighbor order changes the work, not the answer — the same lesson N-Queens' and Graph Coloring's own Pitfalls sections raise about their own orderings. Trying this graph's neighbors in reverse-alphabetical order instead still finds a valid Hamiltonian cycle, but a different one, after a different number of attempts — checked by running the identical search with only the per-vertex neighbor order reversed. Which order happens to be fastest isn't predictable from the graph alone without just running the search.
This isn't "just needs a working search," the same warning Graph Coloring gives about itself. Deciding whether a Hamiltonian path or cycle exists is NP-complete in general — no algorithm, backtracking or otherwise, is known to solve every instance in polynomial time, and pruning (skipping already-visited neighbors, as this demo does) reduces the constant factor but not the underlying exponential order. Small, sparse graphs like this demo's six vertices resolve instantly regardless; the exponential cost is a worst case that shows up on adversarially dense or specifically-constructed larger graphs, not a promise that every graph is this fast.
Time: exponential in the worst case — up to O(n!) walks in the
naive view, though skipping already-visited neighbors (as the reference implementation and demo
both do) prunes this substantially in practice, the same gap between naive brute force and pruned
backtracking that Graph Coloring's own Complexity
section measures for its own problem. Space: O(n) for the visited
array, the walk itself, and the recursion stack, since only one walk's worth of state is ever held
at a time.
This is the site's fourth Backtracking entry, the same extend/reject/backtrack shape as N-Queens, Sudoku, and Graph Coloring, this time building an ordered walk over a graph's vertices instead of assigning a value to each of a fixed set of slots. See Choosing a Backtracking Strategy for how this page's own NP-completeness compares to the other nine entries' rejection rules and known alternatives.