Hamiltonian Path Visualizer

Trace Hamiltonian path search as the algorithm visits vertices, rejects dead ends, and backtracks through an interactive graph.

Current status: Ready. Use the controls to begin exploring Hamiltonian Path.

Hamiltonian Path Visualizer

Click a node to set the starting point
Start: A
Legend
Start Node
On Current Path
Trying This Node
Backtracking

Current Path

1. A
Step
-

What is a Hamiltonian Path?

A Hamiltonian Path visits every vertex in a graph exactly once, using only existing edges. Unlike an Eulerian path (which is about visiting every edge), there's no simple rule for when a Hamiltonian Path exists - the only general approach is to search for one, which is exactly where backtracking comes in.

The search extends the path one node at a time. Whenever it reaches a node with no unvisited neighbors and the path isn't complete yet, it's a dead end - the algorithm removes the last node and tries a different neighbor instead, exactly like the N-Queens Problem undoing a bad placement.

Time & Space Complexity

  • Worst Case TimeO(N!)
  • Space (Recursion + Path)O(N)
  • Problem ClassNP-Complete

Real-World Use Cases

  • Route planning that must visit every stop once
  • DNA fragment assembly and sequencing
  • Circuit board drilling and PCB routing

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

Hamiltonian Path Complete Info Card

BacktrackingGraph Traversal

A Hamiltonian Path search extends a path one node at a time, backing out the moment it reaches a dead end so it can try a different route through the graph.

Algorithm Characteristics

Worst Case Time

Every permutation of nodes may need checking

O(N!)

Space Complexity

Current path plus the visited set

O(N)

Problem Class

No known polynomial-time algorithm exists

NP-Complete

Neighbor Check

Only a node's direct neighbors are considered

O(deg(v))

Search Strategy

Extend the path, recurse, undo on dead end

Depth-First

Guarantee

Not every graph has a Hamiltonian Path

None

Algorithm Steps

1

Start the path at the chosen node

2

Look at the current node's neighbors in order

3

Skip any neighbor already on the path

4

Extend the path to the first unvisited neighbor

5

If a node has no unvisited neighbors, backtrack

6

Stop once the path includes every node

When to Use

  • •Small to moderate graphs where an exact answer is needed
  • •Teaching NP-complete problems and exhaustive search
  • •Verifying whether a specific route covering every stop exists

When to Avoid

  • •Large graphs - the search space grows factorially
  • •When an approximate route is good enough (use heuristics instead)
  • •Dense graphs where many valid paths exist and any one will do
Did You Know? A Hamiltonian Cycle is a Hamiltonian Path that also returns to its starting node - it's the graph problem behind the famous Traveling Salesman Problem.
NP-CompleteGraph searchRoute planning