# Check a graph is Hamiltonian or not (Hamiltonian path)

Hamiltonian path: In this article, we are going to learn how to check is a graph Hamiltonian or not?
Submitted by Souvik Saha, on May 11, 2019

Problem Statement:

Given a graph G. you have to find out that that graph is Hamiltonian or not.

Example:

Input: Output: 1

Because here is a path 0 → 1 → 5 → 3 → 2 → 0 and 0 → 2 → 3 → 5 → 1 → 0

Algorithm:

To solve this problem we follow this approach:

1. We take the source vertex and go for its adjacent not visited vertices.
2. Whenever we find a new vertex we make it source vertex and we repeat step 1.
3. When a vertex count is equal to the vertex number then we check that from vertex is there any path to the source vertex. If there is exist a path to the source vertex then we will mark it and if not then make that vertex as unmarked and continue the process.
4. If there is no such path then we say NO.

## C++ Implementation to check a graph is Hamiltonian or not

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void addedge(list<int>* g, int u, int v)
{
g[u].push_back(v);
g[v].push_back(u);
}

int hamiltonian(list<int>* g, int v, int s, int& count, bool* vis, int& h)
{
if (count > 1 && s == 0) {
h = 1;
return 1;
}
list<int>::iterator it;
for (it = g[s].begin(); it != g[s].end(); it++) {
if (!vis[*it]) {
vis[*it] = true;
count++;
if (count == v) {
vis = false;
}
hamiltonian(g, v, *it, count, vis, h);
vis = true;
vis[*it] = false;
count--;
}
}
return 0;
}

int main()
{
int num;
cin >> num;
for (int i = 0; i < num; i++) {
int v, e;
cin >> v >> e;
list<int> g[v];
int x, y;
for (int j = 0; j < e; j++) {
cin >> x >> y;
}
bool vis[v];
memset(vis, false, sizeof(vis));
int count = 1;
vis = true;
int h = 0;
hamiltonian(g, v, 0, count, vis, h);
cout << h << endl;
}
return 0;
}
```

Output

```1
5
8
0 1
0 2
1 2
1 3
1 4
3 4
3 2
2 4
1
```

TOP Interview Coding Problems/Challenges

Learn PCB Designing: PCB DESIGNING TUTORIAL

 Recommended posts C Tips & Tricks, C++ Tips & Tricks Introduction to Linux (Its modes, Safety, Most popular Applications) Linux Best Distros of 2018 C programming optimization techniques Differences b/w C & Embedded C? Embedded C Interview Q. & A. C programming tips for Embedded Development Basic rules of writing a C program Important points (rules) to remember while writing C/C++ program Top 5 Websites for solving programming challenges Read more...

 Others... Computer G.K. (MCQ) Most viewed pages... Categories...

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates