Hamiltonian Cycle | Backtracking-6

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}.

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

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

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

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.

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

C++

/* C++ program for solution of Hamiltonian
Cycle problem using backtracking */
#include
using namespace std;

// Number of vertices in the graph
#define V 5

void printSolution(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[]’) */
bool isSafe(int v, bool graph[V][V],
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 */ bool hamCycleUtil(bool graph[V][V], 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] == 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. */ bool hamCycle(bool graph[V][V]) { int *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; if (hamCycleUtil(graph, path, 1) == false ) { cout << " Solution does not exist"; return false; } printSolution(path); return true; } /* A utility function to print solution */ void printSolution(int path[]) { cout << "Solution Exists:" " Following is one Hamiltonian Cycle "; for (int i = 0; i < V; i++) cout << path[i] << " "; // Let us print the first vertex again // to show the complete cycle cout << path << " "; cout << endl; } // Driver Code int main() { /* Let us create the following graph (0)--(1)--(2) | / | | / | | / | (3)-------(4) */ bool graph1[V][V] = {{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 hamCycle(graph1); /* Let us create the following graph (0)--(1)--(2) | / | | / | | / | (3) (4) */ bool graph2[V][V] = {{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 hamCycle(graph2); return 0; } // This is code is contributed by rathbhupendra [tabby title="C"]

 /* C program for solution of Hamiltonian Cycle problem    using backtracking */ #include    // Number of vertices in the graph #define V 5    void printSolution(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[]') */ bool isSafe(int v, bool graph[V][V], 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 */ bool hamCycleUtil(bool graph[V][V], 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 ] == 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. */ bool hamCycle(bool graph[V][V]) {     int *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;     if ( hamCycleUtil(graph, path, 1) == false )     {         printf(" Solution does not exist");         return false;     }        printSolution(path);     return true; }    /* A utility function to print solution */ void printSolution(int path[]) {     printf ("Solution Exists:"             " Following is one Hamiltonian Cycle ");     for (int i = 0; i < V; i++)         printf(" %d ", path[i]);        // Let us print the first vertex again to show the complete cycle     printf(" %d ", path);     printf(" "); }    // driver program to test above function int main() {    /* Let us create the following graph       (0)--(1)--(2)        |   /    |        |  /     |        | /     |       (3)-------(4)    */    bool graph1[V][V] = {{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     hamCycle(graph1);       /* Let us create the following graph       (0)--(1)--(2)        |   /    |        |  /     |        | /     |       (3)       (4)    */     bool graph2[V][V] = {{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     hamCycle(graph2);        return 0; }

Java

 /* 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] == 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;         if (hamCycleUtil(graph, path, 1) == false)         {             System.out.println(" Solution 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 + " ");     }        // 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);     } } // This code is contributed by Abhishek Shankhadhar

Python

 # Python program for solution of # hamiltonian cycle problem    class Graph():     def __init__(self, vertices):         self.graph = [[0 for column in range(vertices)]                             for row in range(vertices)]         self.V = vertices        ''' Check if this vertex is an adjacent vertex          of the previously added vertex and is not          included in the path earlier '''     def isSafe(self, v, pos, path):         # Check if current vertex and last vertex          # in path are adjacent         if self.graph[ path[pos-1] ][v] == 0:             return False            # Check if current vertex not already in path         for vertex in path:             if vertex == v:                 return False            return True        # A recursive utility function to solve      # hamiltonian cycle problem     def hamCycleUtil(self, path, pos):            # base case: if all vertices are          # included in the path         if pos == self.V:             # Last vertex must be adjacent to the              # first vertex in path to make a cyle             if self.graph[ path[pos-1] ][ path ] == 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 v in range(1,self.V):                if self.isSafe(v, pos, path) == True:                    path[pos] = v                    if self.hamCycleUtil(path, pos+1) == True:                     return True                    # Remove current vertex if it doesn't                  # lead to a solution                 path[pos] = -1            return False        def hamCycle(self):         path = [-1] * self.V            ''' 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            if self.hamCycleUtil(path,1) == False:             print "Solution does not exist "             return False            self.printSolution(path)         return True        def printSolution(self, path):         print "Solution Exists: Following is one Hamiltonian Cycle"         for vertex in path:             print vertex,         print path, " "    # Driver Code    ''' Let us create the following graph       (0)--(1)--(2)        |   /    |        |  /     |        | /     |       (3)-------(4)    ''' g1 = Graph(5) g1.graph = [ [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 g1.hamCycle();    ''' Let us create the following graph       (0)--(1)--(2)        |   /    |        |  /     |        | /     |       (3)       (4)    ''' g2 = Graph(5) g2.graph = [ [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 g2.hamCycle();    # This code is contributed by Divyanshu Mehta

C#

 // C# program for solution of Hamiltonian  // Cycle problem using backtracking using System;    public class HamiltonianCycle {     readonly 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[]') */     bool 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 */     bool 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] == 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;         if (hamCycleUtil(graph, path, 1) == false)         {             Console.WriteLine(" Solution does not exist");             return 0;         }            printSolution(path);         return 1;     }        /* A utility function to print solution */     void printSolution(int []path)     {         Console.WriteLine("Solution Exists: Following" +                         " is one Hamiltonian Cycle");         for (int i = 0; i < V; i++)             Console.Write(" " + path[i] + " ");            // Let us print the first vertex again         //  to show the complete cycle         Console.WriteLine(" " + path + " ");     }        // Driver code     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);     } }    // This code contributed by Rajput-Ji

Output:

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

Solution does not exist

Note that the above code always prints cycle starting from 0. Starting point should not matter as cycle can be started from any point. If you want to change the starting point, you should make two changes to above code.
Change “path = 0;” to “path = s;” where s is your new starting point. Also change loop “for (int v = 1; v < V; v++)" in hamCycleUtil() to "for (int v = 0; v < V; v++)".