Those who dare to fail miserably can achieve greatly.

Hamiltonian Path and Cycle

Welcome Back Friends!

We hope that you are able to understand the concepts of Graphs and problems based on Graph which have been discussed so far.

Moving further, in this article we will discuss the next problem based on the Graph which is Hamiltonian Path and Cycle.

Prerequisite for this problem is the Find and Print All Paths. In case you have not gone through this problem, it is advised that you solve and understand these first.

Before you move any further, it is advised that you give this problem a fair try.

In this problem you are given a graph and a source vertex. You are required to find and print all "Hamiltonian Paths and Cycles" starting from source. The cycles must end with "*" and paths with a "."

Note:

Print in lexicographically increasing order.
Input has been managed for you.

What is the Hamiltonian Path and Cycle?

A Hamiltonian Path is such a path which visits all vertices without visiting any twice.

A Hamiltonian Path becomes a cycle if there is an edge between the first and last vertex.

For example:

How?

For this graph representation, we have 4 possible Hamiltonian Paths.

Out of these Hamiltonian Paths, 2 are Hamiltonian Cycles as there is edge between start and end vertex of the path.

So we have 4 Hamiltonian Paths and out of those 4, 2 are cycles. So we will add "." at the end of paths and "*" at the end of cycles. Therefore the output will look like:

For better understanding of the question, watch this part of the video lecture.

Approach :

So friend, before we jump to the code of this problem, let me tell you that this problem is very similar to the Print All Paths problem.

In Print All Paths, we used to find the path between a given source and destination vertex. Each time we visited any vertex, we used to set the value corresponding to the vertex as true in the visited array.

And when we were done exploring all neighbor's of this vertex then we again set the value as false corresponding to this vertex in the visited array.

Also if the base case was hit, that is when source becomes equal to destination, we printed the path so far.

We will follow a similar approach in this problem as well.

But this time the base case will change.

Since we need to visit each vertex of the graph this time, the base case will become the stage where all vertices have been visited.

Also, also, also, we need to check that the path obtained is Hamiltonian Path or Hamiltonian Cycle.

For doing so, we check whether there is an edge between source and last visited vertex.

If there is edge than it is Hamiltonian Cycle and we print, "*". And if there is no edge then it is the Hamiltonian Path and we print, ".".

So friend, things might not get clear at first but if you stay with us and gather some patience.

Let's try to code this:

If you remember, Print All Path has exactly the same code, except the base case, which we have not handled yet.

And 2 minor changes can be seen that is Instead of using an array to keep a check for visited vertices, we have used a Hashset and second is that there is an extra parameter, osrc (original source vertex).

Both these changes concern the base case.

We made the first change which is regarding the check for visited, so that while coding the base case, when we need to count the visited number of vertices so far, we can simply use the size of this Hashset instead of using some for loop.

Using Hashset not only eases the coding but also, accessing Hashset's size takes constant time.

For the base case we check whether the size of the visited hashset is equal to one less than the size of the graph.

Why 1 less?

Well, when the call will be made for the last vertex, at that time this last vertex will not be present in the visited Hashset. So, subtracting one from the size of Hashset compensates for the last vertex.

So if the condition (visited.size() == graph.length - 1) is satisfied then the string psf (storing path so far) will get printed.

But we are not done yet! Yes the second change, an extra parameter osrc, storing the original source.

We also need to check whether the psf (path so far) is Hamiltonian Path or Cycle.

To do so, we check whether there is an edge between the osrc vertex (original source vertex) and src vertex (source vertex at this call).

For checking this, we define a variable, closing edge of type Boolean and store false in it.

Then we run a for loop and visit each edge of the original source, and for each edge we check whether the neighbor of osrc equals src.

If it does then we set the value of the closing edge to true and break the loop.

Then we check if the closing edge is true or not.

If it's true, then it implies src and osrc are neighbors and there is an edge between these two, making the particular path Hamiltonian Cycle. So we print "*".

Otherwise it means the closing edge is false and there is no edge between src and osrc, letting it be Hamiltonian Path only. So here we print ".".

Yes! Now that looks complete.

For better understanding of the code and specially the base case, watch this part of the video lecture.

It is also advised that you watch this this part of the video lecture to understand the code using the dry run of the above example using tree representation.

import java.io.*;
import java.util.*;
public class Main {
static class Edge {
int src;
int nbr;
int wt;
Edge(int src, int nbr, int wt) {
this.src = src;
this.nbr = nbr;
this.wt = wt;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int vtces = Integer.parseInt(br.readLine());
ArrayList< Edge>[] graph = new ArrayList[vtces];
for (int i = 0; i < vtces; i++) {
graph[i] = new ArrayList< >();
}
int edges = Integer.parseInt(br.readLine());
for (int i = 0; i < edges; i++) {
String[] parts = br.readLine().split(" ");
int v1 = Integer.parseInt(parts[0]);
int v2 = Integer.parseInt(parts[1]);
int wt = Integer.parseInt(parts[2]);
graph[v1].add(new Edge(v1, v2, wt));
graph[v2].add(new Edge(v2, v1, wt));
}
int src = Integer.parseInt(br.readLine());
HashSet< Integer> visited = new HashSet< >();
hamiltonianPathAndCycle(graph, src, src, visited, src + "");
}
public static void hamiltonianPathAndCycle(ArrayList< Edge>[] graph, int osrc, int src, HashSet< Integer> visited, String psf) {
if (visited.size() == graph.length - 1) {
System.out.print(psf);
boolean closingEdge = false;
for(Edge e: graph[osrc]){
if(e.nbr == src){
closingEdge = true;
break;
}
}
if(closingEdge){
System.out.println("*");
} else {
System.out.println(".");
}
return;
}
visited.add(src);
for (Edge e : graph[src]) {
if (!visited.contains(e.nbr)) {
hamiltonianPathAndCycle(graph, osrc, e.nbr, visited, psf + e.nbr);
}
}
visited.remove(src);
}
}

java;
true";

Analysis

Time Complexity:

O(V+E)

Because of the DFS approach.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.