A graph is a non-linear type of data structure. A graph is defined as a group of vertices, and edges are used to connect these vertices. There are many different types of graphs, such as directed, undirected, weighted, unweighted, cyclic, acyclic, etc. Some applications of graphs include maps, social media, path optimization algorithms, etc.

In this blog, we will discuss counting the total number of hamiltonian paths in a graph. Before diving into the solution, let’s discuss briefly the problem statement once again.

Problem Statement

We are given a directed graph of ‘N’ vertices with vertices labeled from 0 to ‘N - 1’ and 2-D vector ‘edges’ where an edge from ‘a’ to ‘b’ denotes there is a directed edge from a to b, i.e., it is in a single direction only. The main task is to count the total number of hamiltonian paths in the given directed graph where the starting vertex = 0 and the final visited vertex = N - 1.

Note: A hamiltonian path is one in which every vertex in the graph is visited exactly once.

Total number of Hamiltonian paths in the given graph = 2

Explanation

Our graph looks like this:

1st Hamiltonian path starting from 0th vertex and ending at the 4th vertex looks like this:

2nd Hamiltonian path starting from 0th vertex and ending at the 4th vertex looks like this:

Therefore, there are 2 hamiltonian paths for the given input.

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

Solution Approach

The idea is to use Bit Masking with Dynamic Programming. All of the subsets of the given vertices represented by an N-size mask will be iterated over, and count all the hamiltonian path that starts at the 0^{th} vertex and finishes at (N - 1)^{th} vertex.

Let S represents a bitmask with S = 0 to S = (1<< N) - 1 for a graph with N vertices, and dp[i][S] represents the number of paths that visit every vertex in the mask S and end at i then the valid recurrence will be:

dp[i][S] = Summation of all dp[j][S XOR 2^{i}]

Where j belongs to the mask S and there is a directed edge starting from j and ending at i,

Where [S XOR 2^{i}] represents the sub-mask of mask S that does not contain the ith vertex, and there must be a directed edge from j to i.

We will use the top-down or recursive dynamic programming approach to implement the recurrence mentioned above. Let’s take a look at the algorithm of the whole solution approach.

Algorithm

Create a reverse adjacency list ‘rev_adj’ where each node stores from how many other nodes we can reach the current node via a directed edge.

Declare a 2-D dp[N][2^{N}] array with initial values of all the states as -1(which means that this value is not calculated yet). Here, dp[i][j] means the total number of ways such that the last index is ‘i’ and all the vertices in mask ‘j’ are visited.

Call the ‘calculate’ function with initial parameters being last index = N - 1 and initial mask = (1<< N) -1 which indicates all the vertices are visited.

Consider all the possibilities from which we can reach our ‘current’ node by iterating over the ‘prev’ nodes using a reverse adjacency list.

If the ‘prev’ node lies in the mask that means we can reach our current node from the previous node and we will add its contribution to the ‘total’.

Else, just skip this previous node and continue to the next node.

Return the ‘total’ which stores the total number of ways and is displayed as the output.

Dry Run

Initially, we have taken N = 5 so, the last index = 4 (i.e., N - 1) and with mask = ( 2^{N} - 1) = 35 and we will look the all the vertices from the reverse adjacency list from where we can reach the index = 4 which are indexes 1 and 3. Now, similarly, we will go on and look at the two indexes at 1 and 3 and our mask here will change to a new value which is equal to (Mask xor (2 ^ 4)), and similarly, the recursion calls go on.

We used a 2-D dp array to store the results to prevent the solution from reaching an exponential complexity.

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;
// Storing adjacency list
vector <vector <int>> rev_adj;
// Initialising dp array
vector <vector <int>>dp;
int calculate(int current, int mask){
// Base conditions
if(current==0){
if(mask==1){
return 1;
}
else{
return 0;
}
}
// If 0th vertex is absent
if(!(mask & 1)){
return 0;
}
// Already calculated value
if(dp[current][mask]!=-1){
return dp[current][mask];
}
int total=0;
for(auto prev:rev_adj[current]){
// Checking if this index is present in the mask
if(mask & (1<<prev)){
total += calculate(prev, mask ^ (1 << current));
}
}
return dp[current][mask]=total;
}
int main(){
// Total number of vertices in the graph
int N = 5;
// Directed edges of the graph
vector <vector <int>>edges;
edges.push_back({0,2});
edges.push_back({2,3});
edges.push_back({3,1});
edges.push_back({1,3});
edges.push_back({2,1});
edges.push_back({3,4});
edges.push_back({1,4});
rev_adj.assign(N,vector <int>(0));
dp.assign(N,vector <int>((1 << N)));
// Setting all values of dp to 0
for(int i=0;i<N;i++){
for(int j=0;j<(1 << N);j++){
dp[i][j]=-1;
}
}
// Creating reverse adjacency list
for(auto i:edges)
{
// Edge from -> to
int from=i[0];
int to=i[1];
rev_adj[to].push_back(from);
}
cout<<"Total Number of Hamiltonian paths in given graph = ";
/*
Calling the function for the last index N - 1
and visiting all indexes before that.
*/
cout<<calculate(N - 1, (1 << N) - 1);
}

Output

Implementation in Java

import java.util.ArrayList;
public class MyClass {
static int dp[][];
static ArrayList<ArrayList<Integer> > rev_adj;
static int calculate(int current, int mask){
// Base conditions
if(current==0){
if(mask==1){
return 1;
}
else{
return 0;
}
}
// If 0th vertex is absent
if((mask & 1)==0){
return 0;
}
// Already calculated value
if(dp[current][mask]!=-1){
return dp[current][mask];
}
int total=0;
for(int j = 0; j < rev_adj.get(current).size(); j++){
int prev = rev_adj.get(current).get(j);
// Checking if this index is present in the mask
if((mask & (1<<prev))>0){
total += calculate(prev, mask ^ (1 << current));
}
else{
continue;
}
}
return dp[current][mask]=total;
}
// Driver code
public static void main(String args[]) {
// Total number of vertices in the graph
int N = 5;
int limit= (1 << N);
rev_adj = new ArrayList<ArrayList<Integer> >(N);
dp= new int[N][limit];
// Setting all values of dp to 0
for(int i=0;i<N;i++){
for(int j=0;j<(1 << N);j++){
dp[i][j]=-1;
}
}
for (int i = 0; i < N; i++)
rev_adj.add(new ArrayList<Integer>());
//Directed edges of the graph
rev_adj.get(2).add(0);
rev_adj.get(3).add(2);
rev_adj.get(1).add(3);
rev_adj.get(3).add(1);
rev_adj.get(1).add(2);
rev_adj.get(4).add(3);
rev_adj.get(4).add(1);
/*
Calling the function for last index N - 1
and visited all indexes before that.
*/
System.out.print("Total Number of Hamiltonian paths in given graph = ");
System.out.print(calculate(N - 1, (1 << N) - 1));
}
}

Output

Time Complexity

O(N * 2^{N})

Explanation: Total possible masks are 2^{N}, which lies from 0 to 2^{N} - 1, and in the worst case, the total number of possible vertices from which you can reach the current index can be N. So, considering both these factors simultaneously yields a time complexity of O(N * 2^{N}).

Space Complexity

O(N * 2^{N})

Explanation: For storing the results, we declared a 2-D dp array of size (N * 2^{N}) which gives us a total space complexity of O(N * 2^{N}).

Frequently Asked Questions

What is dynamic programming, and where is it used?

Dynamic programming is an optimization method used in various programming problems. It is used in problems where the solution depends on smaller overlapping subproblems. We use it to memorize the results to be used later when needed quickly.

What do you mean by a directed graph?

A directed graph is a collection of connected objects (or vertices or nodes) in which all edges are directed in a single direction from one vertex to another.

What do you mean by a Hamiltonian path?

Each vertex is visited by a Hamiltonian path, with each vertex being precisely visited once (NOT every edge). If it comes to an end at the starting vertex, it is a Hamiltonian cycle.

What do you mean by an Euler path?

A path known as an Euler path is one that precisely traverses each edge only once. If the Euler path ends at the same vertex from which it has started, it is called an Euler cycle.

Write some applications of Dynamic Programming.

DP finds applications in optimization, combinatorial, graph algorithms, and string problems.

Conclusion

In this blog, we discussed a problem based on counting the total number of hamiltonian paths in a directed graph and used dynamic programming along with the bitmasks approach to solving the problem. We saw the algorithm for the approach and implemented the solution in two different languages, C++ and Java. This problem helps us learn more about some complex topics in Data Structures and algorithms.