{"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=”banner”]\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 “PRACTICE<\/u><\/i><\/b>” 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=”banner”]\n
Implementation of Backtracking solution<\/strong>
\nFollowing are implementations of the Backtracking solution.<\/p>\n
java program:<\/p>\n
 
 <\/div> 
\/* Java program for solution of Hamiltonian Cycle problem   using backtracking *\/class HamiltonianCycle{    final int V = 5;    int path[];     \/* A utility function to check if the vertex v can be       added at index 'pos'in the Hamiltonian Cycle       constructed so far (stored in 'path[]') *\/    boolean isSafe(int v, int graph[][], int path[], int pos)    {        \/* Check if this vertex is an adjacent vertex of           the previously added vertex. *\/        if (graph[path[pos - 1]][v] == 0)            return false;         \/* Check if the vertex has already been included.           This step can be optimized by creating an array           of size V *\/        for (int i = 0; i < pos; i++)            if (path[i] == v)                return false;         return true;    }     \/* A recursive utility function to solve hamiltonian       cycle problem *\/    boolean hamCycleUtil(int graph[][], int path[], int pos)    {        \/* base case: If all vertices are included in           Hamiltonian Cycle *\/        if (pos == V)        {            \/\/ And if there is an edge from the last included            \/\/ vertex to the first vertex            if (graph[path[pos - 1]][path[0]] == 1)                return true;            else                return false;        }         \/\/ Try different vertices as a next candidate in        \/\/ Hamiltonian Cycle. We don't try for 0 as we        \/\/ included 0 as starting point in in hamCycle()        for (int v = 1; v < V; v++)        {            \/* Check if this vertex can be added to Hamiltonian               Cycle *\/            if (isSafe(v, graph, path, pos))            {                path[pos] = v;                 \/* recur to construct rest of the path *\/                if (hamCycleUtil(graph, path, pos + 1) == true)                    return true;                 \/* If adding vertex v doesn't lead to a solution,                   then remove it *\/                path[pos] = -1;            }        }         \/* If no vertex can be added to Hamiltonian Cycle           constructed so far, then return false *\/        return false;    }     \/* This function solves the Hamiltonian Cycle problem using       Backtracking. It mainly uses hamCycleUtil() to solve the       problem. It returns false if there is no Hamiltonian Cycle       possible, otherwise return true and prints the path.       Please note that there may be more than one solutions,       this function prints one of the feasible solutions. *\/    int hamCycle(int graph[][])    {        path = new int[V];        for (int i = 0; i < V; i++)            path[i] = -1;         \/* Let us put vertex 0 as the first vertex in the path.           If there is a Hamiltonian Cycle, then the path can be           started from any point of the cycle as the graph is           undirected *\/        path[0] = 0;        if (hamCycleUtil(graph, path, 1) == false)        {            System.out.println("\\nSolution does not exist");            return 0;        }         printSolution(path);        return 1;    }     \/* A utility function to print solution *\/    void printSolution(int path[])    {        System.out.println("Solution Exists: Following" +                           " is one Hamiltonian Cycle");        for (int i = 0; i < V; i++)            System.out.print(" " + path[i] + " ");         \/\/ Let us print the first vertex again to show the        \/\/ complete cycle        System.out.println(" " + path[0] + " ");    }     \/\/ driver program to test above function    public static void main(String args[])    {        HamiltonianCycle hamiltonian =                                new HamiltonianCycle();        \/* Let us create the following graph           (0)--(1)--(2)            |   \/ \\   |            |  \/   \\  |            | \/     \\ |           (3)-------(4)    *\/        int graph1[][] = {{0, 1, 0, 1, 0},            {1, 0, 1, 1, 1},            {0, 1, 0, 0, 1},            {1, 1, 0, 0, 1},            {0, 1, 1, 1, 0},        };         \/\/ Print the solution        hamiltonian.hamCycle(graph1);         \/* Let us create the following graph           (0)--(1)--(2)            |   \/ \\   |            |  \/   \\  |            | \/     \\ |           (3)       (4)    *\/        int graph2[][] = {{0, 1, 0, 1, 0},            {1, 0, 1, 1, 1},            {0, 1, 0, 0, 1},            {1, 1, 0, 0, 0},            {0, 1, 1, 0, 0},        };         \/\/ Print the solution        hamiltonian.hamCycle(graph2);    }}<\/code><\/pre> <\/div>\n[ad type=”banner”]\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}]}}