Count all Hamiltonian paths in a given directed graph

0 0 7 minutes read

Given a directed graph of N vertices valued from 0 to N – 1 and array graph[] of size K represents the Adjacency List of the given graph, the task is to count all Hamiltonian Paths in it which start at the 0^th vertex and end at the (N – 1)^th vertex.

Note: Hamiltonian path is defined as the path which visits every vertex of the graph exactly once.

Examples:

Input: N = 4, K = 6, graph[][] = {{1, 2}, {1, 3}, {2, 3}, {3, 2}, {2, 4}, {3, 4}}
Output: 2
Explanation:
The paths below shown are 1 -> 3 -> 2 -> 4 and 1 -> 2 -> 3 -> 4 starts at 1 and ends at 4 and are called Hamiltonian paths.

Input: N = 2, K = 1, graph[][] = {{1, 2}}
Output: 1

Approach: The given problem can be solved by using Bitmasking with Dynamic Programming, and iterate over all subsets of the given vertices represented by an N size mask and check if there exists a Hamiltonian Path that starts at the 0^th vertex and ends at (N – 1)^th vertex and count all such paths. Let’s say for a graph having N vertices S represents a bitmask where S = 0 to S = (1 << N) -1 and dp[i][S] represents the number of paths that visits every vertex in the mask S and ends at i then the valid recurrence will be given as dp[i][S] = ∑ dp[j][S XOR 2ⁱ] where j ∈ S and there is an edge from j to i where S XOR 2ⁱrepresents the subset which does not have the ith vertex in it and there must be an edge from j to i. Follow the steps below to solve the given problem:

Initialize a 2-D array dp[N][2^N] with 0 and set dp[0][1] as 1.
Iterate over the range from [2, 2^N – 1] using the variable i and check for the mask having all bits set in it.
- Iterate over the range from [0, N) using the variable end and traverse over all bits of the current mask and assume each bit as the ending bit.
  - Initialize the variable prev as i – (1 << end).
  - Iterate over the range [0, size) where size is the size of the array graph[end] using the variable it and traverse over the adjacent vertices of the current ending bit and update the dp[][] array like this dp[end][i] += dp[it][prev].
After performing the above steps, print the value of dp[N-1][2^N – 1] as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all possible paths
void findAllPaths(
    int N, vector<vector<int> >& graph)
{
 
    // Initialize a dp array
    int dp[N][(1 << N)];
 
    // Initialize it with 0
    memset(dp, 0, sizeof dp);
 
    // Initialize for the first vertex
    dp[0][1] = 1;
 
    // Iterate over all the masks
    for (int i = 2; i < (1 << N); i++) {
 
        // If the first vertex is absent
        if ((i & (1 << 0)) == 0)
            continue;
 
        // Only consider the full subsets
        if ((i & (1 << (N - 1)))
            && i != ((1 << N) - 1))
            continue;
 
        // Choose the end city
        for (int end = 0; end < N; end++) {
 
            // If this city is not in the subset
            if (i & (1 << end) == 0)
                continue;
 
            // Set without the end city
            int prev = i - (1 << end);
 
            // Check for the adjacent cities
            for (int it : graph[end]) {
                if ((i & (1 << it))) {
                    dp[end][i] += dp[it][prev];
                }
            }
        }
    }
 
    // Print the answer
    cout << dp[N - 1][(1 << N) - 1];
}
 
// Driver Code
int main()
{
    int N = 4;
    vector<vector<int> > graph(N);
    graph[1].push_back(0);
    graph[2].push_back(0);
    graph[2].push_back(1);
    graph[1].push_back(2);
    graph[3].push_back(1);
    graph[3].push_back(2);
 
    findAllPaths(N, graph);
 
    return 0;
}

Java

//Java program to count all Hamiltonian 
//paths in a given directed graph
 
import java.io.*;
import java.util.*;
 
class GFG {
     
    // Function to find all possible paths
    static void findAllPaths(int N, List<List<Integer>> graph){
         
        // Initialize a dp array
        int dp[][] = new int[N][(1<<N)];
         
        // Initialize it with 0
        for(int i=0;i<N;i++){
            for(int j=0;j<(1<<N);j++){
                dp[i][j]=0;
            }
        }
         
        // Initialize for the first vertex
        dp[0][1] = 1;
      
        // Iterate over all the masks
        for (int i = 2; i < (1 << N); i++) {
      
            // If the first vertex is absent
            if ((i & (1 << 0)) == 0){
                continue;
            }
      
            // Only consider the full subsets
            if ((i & (1 << (N - 1)))==1 && (i != ((1 << N) - 1))){
                continue;
            }
      
            // Choose the end city
            for (int end = 0; end < N; end++) {
      
                // If this city is not in the subset
                if ((i & (1 << end)) == 0){
                    continue;
                }
      
                // Set without the end city
                int prev = i - (1 << end);
      
                // Check for the adjacent cities
                for (int it : graph.get(end)) {
                    if ((i & (1 << it))!=0) {
                        dp[end][i] += dp[it][prev];
                    }
                }
            }
        }
        System.out.print(dp[N - 1][(1 << N) - 1]);
    }
     
    //Driver Code
    public static void main (String[] args) {
        int N=4;
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0;i<N;i++){
            graph.add(new ArrayList<Integer>());
        }
        graph.get(1).add(0);
        graph.get(2).add(0);
        graph.get(2).add(1);
        graph.get(1).add(2);
        graph.get(3).add(1);
        graph.get(3).add(2);
         
        findAllPaths(N, graph);
         
    }
}
 
//This code is contributed by shruti456rawal

Python3

# python program for the above approach
 
# Function to find all possible paths
def findAllPaths(N, graph):
 
        # Initialize a dp array
 
        # Initialize it with 0
    dp = [[0 for _ in range(1 << N)] for _ in range(N)]
 
    # Initialize for the first vertex
    dp[0][1] = 1
 
    # Iterate over all the masks
    for i in range(2, (1 << N)):
 
        # If the first vertex is absent
        if ((i & (1 << 0)) == 0):
            continue
 
         # Only consider the full subsets
        if ((i & (1 << (N - 1)))and i != ((1 << N) - 1)):
            continue
 
        # Choose the end city
        for end in range(0, N):
 
             # If this city is not in the subset
            if (i & (1 << end) == 0):
                continue
 
                # Set without the end city
            prev = i - (1 << end)
 
            # Check for the adjacent cities
 
            for it in graph[end]:
                if ((i & (1 << it))):
                    dp[end][i] += dp[it][prev]
 
        # Print the answer
    print(dp[N - 1][(1 << N) - 1])
 
# Driver Code
if __name__ == "__main__":
 
    N = 4
    graph = [[] for _ in range(N)]
    graph[1].append(0)
    graph[2].append(0)
    graph[2].append(1)
    graph[1].append(2)
    graph[3].append(1)
    graph[3].append(2)
 
    findAllPaths(N, graph)
 
    # This code is contributed by rakeshsahni

Javascript

<script>
// Javascript program for the above approach
 
// Function to find all possible paths
function findAllPaths(N, graph) {
  // Initialize a dp array
  let dp = new Array(N).fill(0).map(() => new Array(1 << N).fill(0));
 
  // Initialize for the first vertex
  dp[0][1] = 1;
 
  // Iterate over all the masks
  for (let i = 2; i < 1 << N; i++) {
    // If the first vertex is absent
    if ((i & (1 << 0)) == 0) continue;
 
    // Only consider the full subsets
    if (i & (1 << (N - 1)) && i != (1 << N) - 1) continue;
 
    // Choose the end city
    for (let end = 0; end < N; end++) {
      // If this city is not in the subset
      if (i & (1 << end == 0)) continue;
 
      // Set without the end city
      let prev = i - (1 << end);
 
      // Check for the adjacent cities
      for (let it of graph[end]) {
        if (i & (1 << it)) {
          dp[end][i] += dp[it][prev];
        }
      }
    }
  }
 
  // Print the answer
  document.write(dp[N - 1][(1 << N) - 1]);
}
 
// Driver Code
 
let N = 4;
let graph = new Array(N).fill(0).map(() => []);
graph[1].push(0);
graph[2].push(0);
graph[2].push(1);
graph[1].push(2);
graph[3].push(1);
graph[3].push(2);
 
findAllPaths(N, graph);
 
// This code is contributed by gfgking.
</script>

C#

//C# program to count all Hamiltonian 
//paths in a given directed graph
 
using System;
using System.Collections.Generic;
 
public class GFG
{
    // Function to find all possible paths
    static void findAllPaths(int N, List<List<int>> graph)
    {
        // Initialize a dp array
        int[][] dp = new int[N][];
        for (int i = 0; i < N; i++)
        {
            dp[i] = new int[1 << N];
        }
 
        // Initialize it with 0
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < (1 << N); j++)
            {
                dp[i][j] = 0;
            }
        }
 
        // Initialize for the first vertex
        dp[0][1] = 1;
 
        // Iterate over all the masks
        for (int i = 2; i < (1 << N); i++)
        {
            // If the first vertex is absent
            if ((i & (1 << 0)) == 0)
            {
                continue;
            }
 
            // Only consider the full subsets
            if ((i & (1 << (N - 1))) == 1 && (i != ((1 << N) - 1)))
            {
                continue;
            }
 
            // Choose the end city
            for (int end = 0; end < N; end++)
            {
                // If this city is not in the subset
                if ((i & (1 << end)) == 0)
                {
                    continue;
                }
 
                // Set without the end city
                int prev = i - (1 << end);
 
                // Check for the adjacent cities
                foreach (int it in graph[end])
                {
                    if ((i & (1 << it)) != 0)
                    {
                        dp[end][i] += dp[it][prev];
                    }
                }
            }
        }
        Console.WriteLine(dp[N - 1][(1 << N) - 1]);
    }
 
    //Driver Code
    public static void Main(string[] args)
    {
        int N = 4;
        List<List<int>> graph = new List<List<int>>();
        for (int i = 0; i < N; i++)
        {
            graph.Add(new List<int>());
        }
        graph[1].Add(0);
        graph[2].Add(0);
        graph[2].Add(1);
        graph[1].Add(2);
        graph[3].Add(1);
        graph[3].Add(2);
 
        findAllPaths(N, graph);
    }
}

Output

Time Complexity: O(N*2^N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!