Skip to main content

Hamiltonian Path / Cycle

Learn Hamiltonian Path / Cycle (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Hamiltonian Path and Cycle A Hamiltonian path visits every vertex exactly once ; a Hamiltonian cycle also returns to the start. Unlike Euler paths there is no simple test : the problem is NP-complete . Small graphs are solved by backtracking : extend the path one vertex at a time, and undo the step when it leads nowhere. The worst case is about O(n!) .

More lessons in Graphs