{"id":26508,"date":"2017-12-20T21:27:45","date_gmt":"2017-12-20T15:57:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26508"},"modified":"2017-12-20T21:27:45","modified_gmt":"2017-12-20T15:57:45","slug":"java-programming-backtracking-hamiltonian-cycle","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-backtracking-hamiltonian-cycle\/","title":{"rendered":"java programming – Backtracking | Set 6 (Hamiltonian Cycle)"},"content":{"rendered":"

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.<\/span> 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.<\/p>\n

Input:<\/em>
\nA 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.<\/p>\n

Output:<\/em>
\nAn 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.<\/p>\n[ad type=\u201dbanner\u201d]\n

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}<\/p>\n

(0)--(1)--(2)\r\n |   \/ \\   |\r\n |  \/   \\  | \r\n | \/     \\ |\r\n(3)-------(4)\r\n<\/pre>\n
And the following graph doesn\u2019t contain any Hamiltonian Cycle.<\/p>\n
(0)--(1)--(2)\r\n |   \/ \\   |\r\n |  \/   \\  | \r\n | \/     \\ |\r\n(3)      (4) \r\n<\/pre>\n
\n
Recommended: Please solve it on \u201cPRACTICE<\/u><\/i><\/b>\u201d first, before moving on to the solution.<\/h2>\n<\/div>\n
Naive Algorithm<\/strong>
\nGenerate all possible configurations of vertices and print a configuration that satisfies the given constraints. There will be n! (n factorial) configurations.<\/p>\n
while there are untried conflagrations\r\n{\r\n   generate the next configuration\r\n   if ( there are edges between two consecutive vertices of this\r\n      configuration and there is an edge from the last vertex to \r\n      the first ).\r\n   {\r\n      print this configuration;\r\n      break;\r\n   }\r\n}\r\n<\/pre>\n
Backtracking Algorithm<\/strong>
\nCreate 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.<\/p>\n[ad type=\u201dbanner\u201d]\n
Implementation of Backtracking solution<\/strong>
\nFollowing are implementations of the Backtracking solution.<\/p>\n
java program:<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%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\u2019pos\u2019in%20the%20Hamiltonian%20Cycle%0A%20%20%20%20%20%20%20constructed%20so%20far%20(stored%20in%20\u2019path%5B%5D\u2019)%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\u2019t%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\u2019t%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)\u2013(1)\u2013(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)\u2014\u2014-(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)\u2013(1)\u2013(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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n
Output:<\/p>\n
Solution Exists: Following is one Hamiltonian Cycle\r\n 0  1  2  4  3  0\r\n\r\nSolution does not exist\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
java programming – Backtracking – Hamiltonian Cycle – Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,73906,78521,2139],"tags":[75507,79012,79014,78968,78965,79011,78967,79013],"class_list":["post-26508","post","type-post","status-publish","format-standard","hentry","category-coding","category-graph-algorithms","category-hard-problems","category-java","tag-algorithm-for-finding-hamiltonian-cycle-in-an-undirected-graph","tag-c-program-for-hamiltonian-cycle-problem","tag-hamiltonian-cycle-algorithm-ppt","tag-hamiltonian-cycle-algorithm-using-backtracking-pdf","tag-hamiltonian-cycle-example","tag-hamiltonian-cycle-using-backtracking-example","tag-hamiltonian-path-algorithm-pseudocode","tag-time-complexity-of-hamiltonian-cycle-using-backtracking"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26508","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26508"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26508\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26508"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26508"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26508"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}