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.


Download   Run Code


Download   Run Code


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

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

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


If I am right, this code is for hamiltonian cycle instead of hamiltonian path