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++ implementation –
 

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 🙂