Hamiltonian Path

A Hamiltonian path is a path that visits each node in a graph exactly once.

Checking the existence of a Hamiltonian path is a NP-Hard problem, and no efficient algorithm is known for solving the problem.

Solve using the Topological Sort.

Hamiltonian Cycle

A Hamiltonian cycle, is a special case of a Hamiltonian path, where the starting and ending vertices are the same, forming a cycle.

• The hamiltonian cycle problem is NP-Complete

Hamiltonian Cycle

A cycle that is a spanning subgraph (i.e., visits all vertices) is called a Hamiltonian cycle.

Determining if a graph has a Hamiltonian cycle or not is in general difficult – it is NP-Complete.