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 0th 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 0th 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 2i] where j ∈ S and there is an edge from j to i where S XOR 2i 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][2N] with 0 and set dp[0][1] as 1.
- Iterate over the range from [2, 2N – 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].
- 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.
- After performing the above steps, print the value of dp[N-1][2N – 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 pathsvoid 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 Codeint 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 graphimport 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 pathsdef 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 Codeif __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 pathsfunction 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 Codelet 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 graphusing 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
2
Time Complexity: O(N*2N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
