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

Thanks for reading.

Please use our online compiler to post code in comments.
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