C++ Programming-Backtracking Set 6 (Hamiltonian Cycle)

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.

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}

|   / \   |
 |  /   \  | 
 | /     \ |
(3)-------(4)

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

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

[ad type=”banner”]

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.

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