How to find Hamiltonian Cycle in a Graph

Question

I am trying to solve the Hamiltonian Cycle problem. I am able to find a path with all the vertices, but unable to complete the cycle.

Can someone provide me with an algorithm to find the cycle?

Answer 1

Determining if a graph has a Hamiltonian Cycle is a NP-complete problem. This means that we can check if a given path is a Hamiltonian cycle in polynomial time, but we don't know any polynomial time algorithms capable of finding it.

The only algorithms that can be used to find a Hamiltonian cycle are exponential time algorithms. Some of them are

• Brute force search
• Dynamic programming
• Other exponential but nevertheless faster algorithms that you can find here

Answer 2

This is one of the most basic problems in computer science, there are plenty solutions depending on what you want: start here http://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms

There are also SO answers related: here and here

Answer 3

I hope this below link which i found will help you lot with clear explanation...... http://www.geeksforgeeks.org/archives/19092

Answer 4

Use a SAT solver if possible. They don't have the good theoretical time limits of the algorithms in the Wikipedia article, but in practice they can often solve them surprisingly quickly.