সি++ প্রোগ্রাম: দেওয়া গ্রাফে হ্যামিল্টোনিয়ান সাইকেল থাকতে হবে কিনা চেক করা

একটি হ্যামিল্টোনিয়ান সাইকেল হলো একটি হ্যামিল্টোনিয়ান পথ যাতে লাস্ট ভার্টেক্স থেকে ফার্স্ট ভার্টেক্স পর্যন্ত একটি এজ (গ্রাফে) থাকে। একটি আনডিরেক্টেড গ্রাফে এটি একটি পথ যা গ্রাফের প্রতিটি ভার্টেক্সকে ঠিক একবার ভিজিট করে।

ফাংশন এবং উদ্দেশ্য

Begin
    1. function isSafe() চেক করে যে এটি পূর্বে যোগ করা ভার্টেক্সের সাথে এডজাসেন্ট কিনা এবং ইতিমধ্যে যোগ করা হয়নি।
    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