# Hamiltonian Path Algorithm with C++

## Overview

In this article, we shall learn about Hamiltonian Paths. A Hamiltonian path in a graph is any path that visits every node exactly once, not less, not more.

## Problem Statement

Given, an undirected graph ‘G’, in its adjacency matrix form, contains ‘n’ nodes. Determine whether or not G consists of any Hamiltonian paths.

## Examples

G = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1, 0, 1, 0, 0}}
Yes, G has a Hamiltonian Path, as shown in the image ahead:

## Brute Force method

One simple solution is to produce every possible permutation of the n nodes. For every permutation, determine whether or not is it a valid hamiltonian path. This is done by checking if there exists an edge between adjacent nodes.

O(N * N!)

O(1)

## An Efficient Alternative

We can use Dynamic-Programming and Bitmasking to optime the aforementioned brute force approach. For each subset ‘s’ of nodes, check if there’s a hamiltonian path in s ending at some node ‘v’ that is present in v. If there exists any node ‘u’ such that it is a neighbor to v, there also will exist a hamiltonian path ending at u. We solve the problem by generalizing the ending node of the Hamiltonian path and the subset of nodes.

## Implementation

 #include "iostream"#include "vector"#include "list"#include "limits.h"#include "stack"#include "unordered_map"#include "unordered_set"#include "set"#include "map"#include "math.h"#include "algorithm"#include "queue"#include "functional"#include "numeric"#include "iomanip"#include "bitset"using namespace std;bool HamiltonianPath(const vector>&g){  int n=g.size();  vector>dp(n, vector(1<>g = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 0 } };  cout<<(HamiltonianPath(g)?"yes":"no")<

Output

 yes
write your code here: Coding Playground