Print all Hamiltonian path present in a graph

Given an undirected graph, print all Hamiltonian paths present in it. Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once.


 

For example, below graph shows a Hamiltonian Path marked in red.

Hamiltonian path

 
The idea is to use backtracking. We check if every edge starting from an unvisited vertex leads to a solution or not. As Hamiltonian path visits each vertex exactly once, we take help of visited[] array in proposed solution to process only unvisited vertices. Also we use path[] array to stores vertices covered in current path. If all the vertices are visited, then Hamiltonian path exists in the graph and we print the complete path stored in path[] array.

C++

Download   Run Code

Java

Download   Run Code

Output:

0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
foobar
Guest
foobar

Couldn’t we leverage the path to check if it is visited instead of tracking the visited seperately? Or am I missing something here?