Search code examples
algorithmhamiltonian-cycle

Enumerate *all* hamiltonian paths

I know this has been asked before, but I did not find its answer in any of the posts. Can someone please suggest me an algorithm which enumerates ALL Hamiltonian paths in a graph?

A little background: I am working on a problem in which I have to enumerate each Hamiltonian path, do some analysis, and return the result. For that, I need to be able to enumerate all the possible hamiltonian paths.

Thanks.

Solution

  • Use BFS/DFS as suggested but don't stop at the first solution. BFS/DFS primary use (in this case) will be to find all of the solution, you need to put a condition to it to stop at the first one.