হ্যামিল্টোনিয়ান সাইকেল হলো একটি হ্যামিল্টোনিয়ান পথ যাতে লাস্ট ভার্টেক্স থেকে ফার্স্ট ভার্টেক্সে এজ থাকে। এটি একটি আনডিরেক্টেড গ্রাফে এমন একটি পথ যা গ্রাফের প্রতিটি ভার্টেক্সকে ঠিক একবার ভিজিট করে।
ফাংশন ও উদ্দেশ্য
Begin
1. function isSafe() - চেক করে নেওয়া ভার্টেক্স পূর্বে যোগ করা ভার্টেক্সের সাথে অadyacent কিনা এবং ইতিমধ্যে যোগ করা হয়নি।
2. function hamiltonianCycle() - হ্যামিল্টোনিয়ান সমস্যা সমাধান করে।
3. function hamCycle() - hamiltonianCycle() ব্যবহার করে সমাধান করে। যদি সাইকেল না থাকে false রিটার্ন করে, অন্যথায় true রিটার্ন করে এবং পথ প্রিন্ট করে।
End
উদাহরণ
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 5
using namespace std;
void displaytheSolution(int path[]);
bool isSafe(int n, bool g[N][N], int path[], int pos) {
if (g[path[pos-1]][n] == 0) return false;
for (int i = 0; i < pos; i++)
if (path[i] == n) return false;
return true;
}
bool hamiltonianCycle(bool g[N][N], int path[], int pos) {
if (pos == N) {
if (g[path[pos-1]][path[0]] == 1) return true;
else return false;
}
for (int n = 1; n < N; n++) {
if (isSafe(n, g, path, pos)) {
path[pos] = n;
if (hamiltonianCycle(g, path, pos+1) == true) return true;
path[pos] = -1;
}
}
return false;
}
bool hamCycle(bool g[N][N]) {
int *path = new int[N];
for (int i = 0; i < N; i++) path[i] = -1;
path[0] = 0;
if (hamiltonianCycle(g, path, 1) == false) {
cout << "\nCycle does not exist" << endl;
return false;
}
displaytheSolution(path);
return true;
}
void displaytheSolution(int p[]) {
cout << "Cycle Exists:";
cout << " Following is one Hamiltonian Cycle \n" << endl;
for (int i = 0; i < N; i++) cout << p[i] << " ";
cout << p[0] << endl;
}
int main() {
bool g[N][N] = {
{0, 1, 0, 1, 1},
{0, 0, 1, 1, 0},
{0, 1, 0, 1, 1},
{1, 1, 1, 0, 1},
{0, 1, 1, 0, 0}
};
hamCycle(g);
return 0;
}
আউটপুট
Cycle Exists: Following is one Hamiltonian Cycle 0 4 1 2 3 0
