Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Naive Approach
2.1.
Algorithm
3.
Optimized Approach(Backtracking)
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Which is Backtracking Algorithm? 
4.2.
What is the difference between Breadth-first Search and Depth-first search? 
4.3.
What is the maximum number of edges in the undirected graph of Nodes N? 
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Implement Hamiltonian Cycle

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM
DSA Problems

Introduction

The problem states that we need to implement the hamiltonian cycle in an undirected graph. 

The Hamiltonian cycle is a path through a graph (See, Data Structures) (can be directed or undirected) that starts and ends at the same vertex, let say i,  and includes every other vertex exactly once. 

We are given a graph and we need to determine whether the given graph contains the Hamiltonian path or not. If there are multiple paths, print any one path, otherwise print “No path possible” if the path is not available. 

Also see, Backtracking and Recursion, and Euclid GCD Algorithm

Input:

A graph is given in the format of a V x V matrix, where V is the number of vertices. A graph[i][j] = 1, if there is edge between i and j, otherwise graph[i][j] = 0. 

Output: 

Print the Hamiltonian cycle if it exists otherwise print “No path possible”. 

Sample Example

Input:

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

 

Visual Representation:

Illustration Image

Output

Following is the hamiltonian cycle: 0 1 2 4 3 0 

Explanation:
Each vertex is visited only once in this path, so it is a hamiltonian cycle. 

Recommended topic, kth largest element in an array

Naive Approach

Generate all possible paths from these vertices, and print that path that satisfies the above constraints. There are N! Paths possible.  

Algorithm

  1. Start generating all the paths taking vertex 0 as the first vertex.
  2. For every path, if it satisfies the constraint of the Hamiltonian path then print this path and break.
  3. Otherwise, keep on trying on every new path. 
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach(Backtracking)

We will use a backtracking algorithm to find the Hamiltonian path. Firstly, we will create a path array that will store the Hamiltonian path, and insert 0 in it initially,  We will mainly create two functions, i.e, isValid(v, k) that will check whether placing v in position k is valid or not and cycleFound(k), it will return true if there is Hamiltonian cycle otherwise returns false. 

Algorithm

isValid(v,k) function: 

If there is no edge between node(k-1) and v or v is already taken, then returns false.
Otherwise, returns true. 

 

cycleFound(node k) function:

if all nodes are included, then
  if the nodes k and 0 have a common edge, then
      return true
    else
      return false;
for all vertex v except source point, do
    if isValid(v, k) return true, then 
      add v into the path
      if cycleFound(k+1) is true, then
          return true
      otherwise, remove v from the path
Done
      return false

 

Implementation in C++

#include<iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {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},
};
   
/* int graph[NODE][NODE] = {
   {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},
}; */

int path[NODE];

void displayCycle() {
   cout<<  " Following is the hamiltonian cycle: ";

   for (int i = 0; i < NODE; i++)
      cout << path[i] << " ";
   cout << path[0] << endl;      //print the first vertex again
}

bool isValid(int v, int k) {
   if (graph [path[k-1]][v] == 0)   //if there is no edge
      return false;

   for (int i = 0; i < k; i++)   //if vertex is already taken, skip that
      if (path[i] == v)
         return false;
   return true;
}

bool cycleFound(int k) {
   if (k == NODE) {             //when all vertices are in the path
      if (graph[path[k-1]][ path[0] ] == 1 )
         return true;
      else
         return false;
   }

   for (int v = 1; v < NODE; v++) {       //for all vertices except starting point
      if (isValid(v,k)) {                //if possible to add v in the path
         path[k] = v;
         if (cycleFound (k+1) == true)
            return true;
         path[k] = -1;               //when k vertex will not in the solution
      }
   }
   return false;
}

bool hamiltonianCycle() {
   for (int i = 0; i < NODE; i++)
      path[i] = -1;
   path[0] = 0; //first vertex as 0

   if ( cycleFound(1) == false ) {
      cout << "No path possible"<<endl;
      return false;
   }

   displayCycle();
   return true;
}

int main() {
   hamiltonianCycle();
}

 

Output:

Following is the hamiltonian cycle: 0 1 2 4 3 0

 

Complexity Analysis

Time Complexity: O(|N))

Space Complexity: O(| V |)

This space will be used by a path array that will store the Hamiltonian path, and its maximum length can be equal to the vertices of the graph.

Frequently Asked Questions

Which is Backtracking Algorithm? 

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time.

What is the difference between Breadth-first Search and Depth-first search? 

The BFS uses a queue data structure while DFS uses the stack data structure. BFS is more suitable for searching vertices closer to the given source, while DFS is more suitable for solutions away from the source.

What is the maximum number of edges in the undirected graph of Nodes N? 

Each node can have an edge over every other n-1 node in an undirected graph. Therefore the total number of edges possible is n*(n-1)/2.

Conclusion

In this article, we discussed the problem of implementing the Hamiltonian Path. We hope you understand the problem and solution properly. Now you can do more similar questions. 

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Check out this problem - Root To Leaf Path

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, Keep Learning and Keep Coding.

Previous article
Minimize operations to transform A to B by multiplying by 2 or appending 1 to it
Next article
The K-th Lexicographical String of All Happy Strings of Length ‘N’
Live masterclass