Given an adjacency matrix adj[][] of an undirected graph consisting of N vertices, the task is to find whether the graph contains a Hamiltonian Path or not. If found to be true, then print “Yes”. Otherwise, print “No”.
A Hamiltonian path is defined as the path in a directed or undirected graph which visits each and every vertex of the graph exactly once.
Examples:
Input: adj[][] = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1, 0, 1, 0, 0}}
Output: Yes
Explanation:
There exists a Hamiltonian Path for the given graph as shown in the image below:
Input: adj[][] = {{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0}}
Output: No
Naive Approach: The simplest approach to solve the given problem is to generate all the possible permutations of N vertices. For each permutation, check if it is a valid Hamiltonian path by checking if there is an edge between adjacent vertices or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Time Complexity: O(N * N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by using Dynamic Programming and Bit Masking which is based on the following observations:
- The idea is such that for every subset S of vertices, check whether there is a hamiltonian path in the subset S that ends at vertex v where v € S.
- If v has a neighbor u, where u € S – {v}, therefore, there exists a Hamiltonian path that ends at vertex u.
- The problem can be solved by generalizing the subset of vertices and the ending vertex of the Hamiltonian path.
Follow the steps below to solve the problem:
- Initialize a boolean matrix dp[][] in dimension N*2N where dp[j ][i] represents whether there exists a path in the subset or not represented by the mask i that visits each and every vertex in i once and ends at vertex j.
- For the base case, update dp[i][1 << i] = true, for i in range [0, N – 1]
- Iterate over the range [1, 2N – 1] using the variable i and perform the following steps:
- All the vertices with bits set in mask i, are included in the subset.
- Iterate over the range [1, N] using the variable j that will represent the end vertex of the hamiltonian path of current subset mask i and perform the following steps:
- If the value of i and 2j is true, then iterate over the range [1, N] using the variable k and if the value of dp[k][i^2j] is true, then mark dp[j][i] is true and break out of the loop.
- Otherwise, continue to the next iteration.
- Iterate over the range using the variable i and if the value of dp[i][2N – 1] is true, then there exists a hamiltonian path ending at vertex i. Therefore, print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int N = 5;// Function to check whether there// exists a Hamiltonian Path or notbool Hamiltonian_path( vector<vector<int> >& adj, int N){ int dp[N][(1 << N)]; // Initialize the table memset(dp, 0, sizeof dp); // Set all dp[i][(1 << i)] to // true for (int i = 0; i < N; i++) dp[i][(1 << i)] = true; // Iterate over each subset // of nodes for (int i = 0; i < (1 << N); i++) { for (int j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if (i & (1 << j)) { // Find K, neighbour of j // also present in the // current subset for (int k = 0; k < N; k++) { if (i & (1 << k) && adj[k][j] && j != k && dp[k][i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j][i] = true; break; } } } } } // Traverse the vertices for (int i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i][(1 << N) - 1]) return true; } // Otherwise, return false return false;}// Driver Codeint main(){ // Input vector<vector<int> > adj = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 0 } }; int N = adj.size(); // Function Call if (Hamiltonian_path(adj, N)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to check whether there// exists a Hamiltonian Path or notstatic boolean Hamiltonian_path(int adj[][], int N){ boolean dp[][] = new boolean[N][(1 << N)]; // Set all dp[i][(1 << i)] to // true for(int i = 0; i < N; i++) dp[i][(1 << i)] = true; // Iterate over each subset // of nodes for(int i = 0; i < (1 << N); i++) { for(int j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if ((i & (1 << j)) != 0) { // Find K, neighbour of j // also present in the // current subset for(int k = 0; k < N; k++) { if ((i & (1 << k)) != 0 && adj[k][j] == 1 && j != k && dp[k][i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j][i] = true; break; } } } } } // Traverse the vertices for(int i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i][(1 << N) - 1]) return true; } // Otherwise, return false return false;}// Driver Codepublic static void main(String[] args){ int adj[][] = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 0 } }; int N = adj.length; // Function Call if (Hamiltonian_path(adj, N)) System.out.println("YES"); else System.out.println("NO");}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to check whether there# exists a Hamiltonian Path or notdef Hamiltonian_path(adj, N): dp = [[False for i in range(1 << N)] for j in range(N)] # Set all dp[i][(1 << i)] to # true for i in range(N): dp[i][1 << i] = True # Iterate over each subset # of nodes for i in range(1 << N): for j in range(N): # If the jth nodes is included # in the current subset if ((i & (1 << j)) != 0): # Find K, neighbour of j # also present in the # current subset for k in range(N): if ((i & (1 << k)) != 0 and adj[k][j] == 1 and j != k and dp[k][i ^ (1 << j)]): # Update dp[j][i] # to true dp[j][i] = True break # Traverse the vertices for i in range(N): # Hamiltonian Path exists if (dp[i][(1 << N) - 1]): return True # Otherwise, return false return False# Driver Codeadj = [ [ 0, 1, 1, 1, 0 ] , [ 1, 0, 1, 0, 1 ], [ 1, 1, 0, 1, 1 ], [ 1, 0, 1, 0, 0 ] ]N = len(adj)if (Hamiltonian_path(adj, N)): print("YES")else: print("NO")# This code is contributed by maheshwaripiyush9 |
C#
// C# program for the above approachusing System;class GFG{// Function to check whether there// exists a Hamiltonian Path or notstatic bool Hamiltonian_path(int[,] adj, int N){ bool[,] dp = new bool[N, (1 << N)]; // Set all dp[i][(1 << i)] to // true for(int i = 0; i < N; i++) dp[i, (1 << i)] = true; // Iterate over each subset // of nodes for(int i = 0; i < (1 << N); i++) { for(int j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if ((i & (1 << j)) != 0) { // Find K, neighbour of j // also present in the // current subset for(int k = 0; k < N; k++) { if ((i & (1 << k)) != 0 && adj[k, j] == 1 && j != k && dp[k, i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j, i] = true; break; } } } } } // Traverse the vertices for(int i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i, (1 << N) - 1]) return true; } // Otherwise, return false return false;}// Driver Codepublic static void Main(String[] args){ int[,] adj = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 0 } }; int N = adj.GetLength(0); // Function Call if (Hamiltonian_path(adj, N)) Console.WriteLine("YES"); else Console.WriteLine("NO");}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program for the above approachvar N = 5;// Function to check whether there// exists a Hamiltonian Path or notfunction Hamiltonian_path( adj, N){ var dp = Array.from(Array(N), ()=> Array(1 << N).fill(0)); // Set all dp[i][(1 << i)] to // true for (var i = 0; i < N; i++) dp[i][(1 << i)] = true; // Iterate over each subset // of nodes for (var i = 0; i < (1 << N); i++) { for (var j = 0; j < N; j++) { // If the jth nodes is included // in the current subset if (i & (1 << j)) { // Find K, neighbour of j // also present in the // current subset for (var k = 0; k < N; k++) { if (i & (1 << k) && adj[k][j] && j != k && dp[k][i ^ (1 << j)]) { // Update dp[j][i] // to true dp[j][i] = true; break; } } } } } // Traverse the vertices for (var i = 0; i < N; i++) { // Hamiltonian Path exists if (dp[i][(1 << N) - 1]) return true; } // Otherwise, return false return false;}// Driver Code// Inputvar adj = [ [ 0, 1, 1, 1, 0 ], [ 1, 0, 1, 0, 1 ], [ 1, 1, 0, 1, 1 ], [ 1, 0, 1, 0, 0 ] ];var N = adj.length;// Function Callif (Hamiltonian_path(adj, N)) document.write( "YES");else document.write( "NO");</script> |
Output:
YES
Time Complexity: O(N2 * 2N)
Auxiliary Space: O(N * 2N)
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!
