Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path. Determine whether a given graph contains Hamiltonian Cycle or not. If it contains, then print the path. Following are the input and output of the required function.

Input:
A 2D array graph[V][V] where V is the number of vertices in graph and graph[V][V] is adjacency matrix representation of the graph. A value graph[i][j] is 1 if there is a direct edge from i to j, otherwise graph[i][j] is 0.

Output:
An array path[V] that should contain the Hamiltonian Path. path[i] should represent the ith vertex in the Hamiltonian Path. The code should also return false if there is no Hamiltonian Cycle in the graph.

[ad type=”banner”]

For example, a Hamiltonian Cycle in the following graph is {0, 1, 2, 4, 3, 0}. There are more Hamiltonian Cycles in the graph like {0, 3, 4, 2, 1, 0}

(0)--(1)--(2)
 |   / \   |
 |  /   \  | 
 | /     \ |
(3)-------(4)

And the following graph doesn’t contain any Hamiltonian Cycle.

(0)--(1)--(2)
 |   / \   |
 |  /   \  | 
 | /     \ |
(3)      (4) 

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Naive Algorithm
Generate all possible configurations of vertices and print a configuration that satisfies the given constraints. There will be n! (n factorial) configurations.

while there are untried conflagrations
{
   generate the next configuration
   if ( there are edges between two consecutive vertices of this
      configuration and there is an edge from the last vertex to 
      the first ).
   {
      print this configuration;
      break;
   }
}

Backtracking Algorithm
Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex and not already added. If we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return false.

[ad type=”banner”]

Implementation of Backtracking solution
Following are implementations of the Backtracking solution.

java program:

[pastacode lang=”java” manual=”%2F*%20Java%20program%20for%20solution%20of%20Hamiltonian%20Cycle%20problem%0A%20%20%20using%20backtracking%20*%2F%0Aclass%20HamiltonianCycle%0A%7B%0A%20%20%20%20final%20int%20V%20%3D%205%3B%0A%20%20%20%20int%20path%5B%5D%3B%0A%20%0A%20%20%20%20%2F*%20A%20utility%20function%20to%20check%20if%20the%20vertex%20v%20can%20be%0A%20%20%20%20%20%20%20added%20at%20index%20’pos’in%20the%20Hamiltonian%20Cycle%0A%20%20%20%20%20%20%20constructed%20so%20far%20(stored%20in%20’path%5B%5D’)%20*%2F%0A%20%20%20%20boolean%20isSafe(int%20v%2C%20int%20graph%5B%5D%5B%5D%2C%20int%20path%5B%5D%2C%20int%20pos)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20Check%20if%20this%20vertex%20is%20an%20adjacent%20vertex%20of%0A%20%20%20%20%20%20%20%20%20%20%20the%20previously%20added%20vertex.%20*%2F%0A%20%20%20%20%20%20%20%20if%20(graph%5Bpath%5Bpos%20-%201%5D%5D%5Bv%5D%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Check%20if%20the%20vertex%20has%20already%20been%20included.%0A%20%20%20%20%20%20%20%20%20%20%20This%20step%20can%20be%20optimized%20by%20creating%20an%20array%0A%20%20%20%20%20%20%20%20%20%20%20of%20size%20V%20*%2F%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20pos%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(path%5Bi%5D%20%3D%3D%20v)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20A%20recursive%20utility%20function%20to%20solve%20hamiltonian%0A%20%20%20%20%20%20%20cycle%20problem%20*%2F%0A%20%20%20%20boolean%20hamCycleUtil(int%20graph%5B%5D%5B%5D%2C%20int%20path%5B%5D%2C%20int%20pos)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F*%20base%20case%3A%20If%20all%20vertices%20are%20included%20in%0A%20%20%20%20%20%20%20%20%20%20%20Hamiltonian%20Cycle%20*%2F%0A%20%20%20%20%20%20%20%20if%20(pos%20%3D%3D%20V)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20And%20if%20there%20is%20an%20edge%20from%20the%20last%20included%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20vertex%20to%20the%20first%20vertex%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(graph%5Bpath%5Bpos%20-%201%5D%5D%5Bpath%5B0%5D%5D%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Try%20different%20vertices%20as%20a%20next%20candidate%20in%0A%20%20%20%20%20%20%20%20%2F%2F%20Hamiltonian%20Cycle.%20We%20don’t%20try%20for%200%20as%20we%0A%20%20%20%20%20%20%20%20%2F%2F%20included%200%20as%20starting%20point%20in%20in%20hamCycle()%0A%20%20%20%20%20%20%20%20for%20(int%20v%20%3D%201%3B%20v%20%3C%20V%3B%20v%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20Check%20if%20this%20vertex%20can%20be%20added%20to%20Hamiltonian%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Cycle%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(isSafe(v%2C%20graph%2C%20path%2C%20pos))%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20path%5Bpos%5D%20%3D%20v%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20recur%20to%20construct%20rest%20of%20the%20path%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(hamCycleUtil(graph%2C%20path%2C%20pos%20%2B%201)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20If%20adding%20vertex%20v%20doesn’t%20lead%20to%20a%20solution%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20then%20remove%20it%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20path%5Bpos%5D%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20no%20vertex%20can%20be%20added%20to%20Hamiltonian%20Cycle%0A%20%20%20%20%20%20%20%20%20%20%20constructed%20so%20far%2C%20then%20return%20false%20*%2F%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20This%20function%20solves%20the%20Hamiltonian%20Cycle%20problem%20using%0A%20%20%20%20%20%20%20Backtracking.%20It%20mainly%20uses%20hamCycleUtil()%20to%20solve%20the%0A%20%20%20%20%20%20%20problem.%20It%20returns%20false%20if%20there%20is%20no%20Hamiltonian%20Cycle%0A%20%20%20%20%20%20%20possible%2C%20otherwise%20return%20true%20and%20prints%20the%20path.%0A%20%20%20%20%20%20%20Please%20note%20that%20there%20may%20be%20more%20than%20one%20solutions%2C%0A%20%20%20%20%20%20%20this%20function%20prints%20one%20of%20the%20feasible%20solutions.%20*%2F%0A%20%20%20%20int%20hamCycle(int%20graph%5B%5D%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20path%20%3D%20new%20int%5BV%5D%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20path%5Bi%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20put%20vertex%200%20as%20the%20first%20vertex%20in%20the%20path.%0A%20%20%20%20%20%20%20%20%20%20%20If%20there%20is%20a%20Hamiltonian%20Cycle%2C%20then%20the%20path%20can%20be%0A%20%20%20%20%20%20%20%20%20%20%20started%20from%20any%20point%20of%20the%20cycle%20as%20the%20graph%20is%0A%20%20%20%20%20%20%20%20%20%20%20undirected%20*%2F%0A%20%20%20%20%20%20%20%20path%5B0%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20if%20(hamCycleUtil(graph%2C%20path%2C%201)%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22%5CnSolution%20does%20not%20exist%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20printSolution(path)%3B%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20A%20utility%20function%20to%20print%20solution%20*%2F%0A%20%20%20%20void%20printSolution(int%20path%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20System.out.println(%22Solution%20Exists%3A%20Following%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%20is%20one%20Hamiltonian%20Cycle%22)%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(%22%20%22%20%2B%20path%5Bi%5D%20%2B%20%22%20%22)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Let%20us%20print%20the%20first%20vertex%20again%20to%20show%20the%0A%20%20%20%20%20%20%20%20%2F%2F%20complete%20cycle%0A%20%20%20%20%20%20%20%20System.out.println(%22%20%22%20%2B%20path%5B0%5D%20%2B%20%22%20%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20driver%20program%20to%20test%20above%20function%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20HamiltonianCycle%20hamiltonian%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20new%20HamiltonianCycle()%3B%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20the%20following%20graph%0A%20%20%20%20%20%20%20%20%20%20%20(0)–(1)–(2)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%20%2F%20%5C%20%20%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%2F%20%20%20%5C%20%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%2F%20%20%20%20%20%5C%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20(3)——-(4)%20%20%20%20*%2F%0A%20%20%20%20%20%20%20%20int%20graph1%5B%5D%5B%5D%20%3D%20%7B%7B0%2C%201%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%200%2C%201%2C%201%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%201%2C%200%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%201%2C%200%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%201%2C%201%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Print%20the%20solution%0A%20%20%20%20%20%20%20%20hamiltonian.hamCycle(graph1)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Let%20us%20create%20the%20following%20graph%0A%20%20%20%20%20%20%20%20%20%20%20(0)–(1)–(2)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%20%2F%20%5C%20%20%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%20%2F%20%20%20%5C%20%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7C%20%2F%20%20%20%20%20%5C%20%7C%0A%20%20%20%20%20%20%20%20%20%20%20(3)%20%20%20%20%20%20%20(4)%20%20%20%20*%2F%0A%20%20%20%20%20%20%20%20int%20graph2%5B%5D%5B%5D%20%3D%20%7B%7B0%2C%201%2C%200%2C%201%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%200%2C%201%2C%201%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%201%2C%200%2C%200%2C%201%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%201%2C%200%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%201%2C%201%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Print%20the%20solution%0A%20%20%20%20%20%20%20%20hamiltonian.hamCycle(graph2)%3B%0A%20%20%20%20%7D%0A%7D%0A” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]

Output:

Solution Exists: Following is one Hamiltonian Cycle
 0  1  2  4  3  0

Solution does not exist