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();
}
You can also try this code with Online C++ Compiler
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.
34+ registered 
