A Hamiltonian path in a graph is a path whereby each node is visited exactly once.

A number of graph-related problems require determining if the interconnections between its edges and vertices form a proper Hamiltonian tour, such as traveling salesperson type problems. Such a problem is NP-Complete, that is, the effort required to solve the problem increases dramatically as the size of the problem grows.

This C++ implementation borrows heavily from the ideas and algorithms used in the following article:

http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/

Continue reading ‘Determining if paths are Hamiltonian in C++’ »