Assignments 7: Write a non-recursive program to check whether Hamiltonian path exists in undirected graph or not. If exists print it. (backtracking).

 Problem Statement: Write a non-recursive program to check whether Hamiltonian path exists in undirected graph or not. If exists print it. (backtracking).

THEORY:

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 the 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 prints 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.

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.

Code with Recursive Method

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

#define N 5

void displaytheSolution(int path[]);

bool isSafe(int n, bool g[N][N], int path[], int pos) {

   if (g [path[pos-1]][n] == 0)

      return false;

   for (int i = 0; i < pos; i++)

      if (path[i] == n)

         return false;

   return true;

}

bool hamiltonianCycle(bool g[N][N], int path[], int pos) {

   //If all vertices are included in Hamiltonian Cycle

   if (pos == N) {

      if (g[ path[pos-1] ][ path[0] ] == 1){

         displaytheSolution(path);

         return true;

      }else

        return false;

   }

   bool res = false;

   for (int n = 1; n < N; n++) {

      if (isSafe(n, g, path, pos)) { //Check if this vertex can be added to Hamiltonian Cycle

         path[pos] = n;

         //recur to construct rest of the path

         res = hamiltonianCycle (g, path, pos+1) || res;

         path[pos] = -1; //remove vertex if it doesn’t lead to the solution

      }

   }

   return res;

}

bool hamCycle(bool g[N][N]) {

   int *path = new int[N];

   for (int i = 0; i < N; i++)

   path[i] = -1;

   //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 (hamiltonianCycle(g, path, 1) == false) {

      cout<<"\nCycle does not exist"<<endl;

      return false;

   }

   

   return true;

}

void displaytheSolution(int p[]) {

   cout<<"Cycle Exists:";

   cout<<" Following is one Hamiltonian Cycle \n"<<endl;

   for (int i = 0; i < N; i++)

   cout<<p[i]<<" ";

   cout<< p[0]<<endl;

}

int main() {

   bool g[N][N] = {

      {0, 1, 1, 1, 1},

{1, 0, 1, 1, 1},

      {1, 1, 0, 1, 1},

      {1, 1, 1, 0, 1},

      {1, 1, 1, 1, 0},

   };

   hamCycle(g);

   return 0;

}

Output

 

Code with Non- Recursive Method

Coming Soon