INPUT GRAPH:
SOURCE CODE:
#include <iostream>
#include <vector>
using namespace std;
void printCycle(const vector<int>& path)
{
cout << "Hamiltonian Cycle: ";
for (int i = 0; i < path.size(); i++)
{
cout << path[i] << " -> ";
}
cout << path[0] << endl;
}
bool isSafe(int v, const vector<vector<int> >& graph, const vector<int>& path, int pos)
{
if (graph[path[pos - 1]][v] == 0)
{
return false;
}
for (int i = 0; i < pos; i++)
{
if (path[i] == v)
{
return false;
}
}
return true;
}
void hamiltonianCycleUtil(vector<vector<int> >& graph, vector<int>& path, int pos, int&
cycleCount, int& iteration)
{
if (pos == graph.size())
{
if (graph[path[pos - 1]][path[0]] == 1)
{
cycleCount++;
cout << "New Hamiltonian Cycle Found - ";
printCycle(path);
}
return;
}
for (int v = 1; v < graph.size(); v++)
{
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
for (int i = 0; i <= pos; i++)
{
cout << path[i];
if (i != pos)
{
cout << " -> ";
}
}
cout << endl;
hamiltonianCycleUtil(graph, path, pos + 1, cycleCount, iteration);
path[pos] = -1;
}
}
}
void hamiltonianCycle(vector<vector<int> >& graph)
{
int V = graph.size();
vector<int> path(V, -1);
int cycleCount = 0;
int iteration = 1;
path[0] = 0;
hamiltonianCycleUtil(graph, path, 1, cycleCount, iteration);
if (cycleCount == 0)
{
cout << "No Hamiltonian Cycle exists" << endl;
}
else
{
cout << "Total Hamiltonian Cycles found: " << cycleCount << endl;
}
}
int main()
{
int V;
cout << "HAMILTONIAN CYCLE" << endl;
cout << "Enter the number of vertices: ";
cin >> V;
vector<vector<int> > graph(V, vector<int>(V, 0));
cout << "Enter the adjacency matrix:" << endl;
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
cin >> graph[i][j];
}
}
cout<<"\nResult is:"<<endl;
hamiltonianCycle(graph);
return 0;
}
INPUT AND OUTPUT:
OUTPUT GRAPH:
CYCLE 1
CYCLE 2
CYCLE 3
CYCLE 4
CYCLE 5
CYCLE 6
