एक हैमिल्टोनियन साइकिल एक हैमिल्टोनियन पथ है जैसे कि हैमिल्टोनियन पथ के अंतिम वर्टेक्स से पहले वर्टेक्स तक एक एज (ग्राफ में) है। यह एक अनडायरेक्टेड ग्राफ में एक पथ है जो ग्राफ के प्रत्येक वर्टेक्स को ठीक एक बार विजिट करता है।
फंक्शन्स और उद्देश्य
- isSafe(): जांचता है कि क्या वर्टेक्स पहले से जोड़े गए वर्टेक्स से एडजेसेंट है और पहले से नहीं जोड़ा गया है।
- hamiltonianCycle(): हैमिल्टोनियन समस्या को हल करता है।
- hamCycle(): हैमिल्टोनियन समस्या को हल करने के लिए
hamiltonianCycle()का उपयोग करता है। यदि हैमिल्टोनियन साइकिल संभव नहीं है तो false लौटाता है, अन्यथा true लौटाता है और पथ प्रिंट करता है।
C++ कार्यान्वयन
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 5
using namespace std;
void displaySolution(int path[]);
bool isSafe(int v, bool graph[N][N], 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;
}
bool hamiltonianCycleUtil(bool graph[N][N], int path[], int pos) {
if (pos == N) {
if (graph[path[pos-1]][path[0]] == 1) return true;
else return false;
}
for (int v = 1; v < N; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamiltonianCycleUtil(graph, path, pos+1)) return true;
path[pos] = -1;
}
}
return false;
}
bool hamCycle(bool graph[N][N]) {
int *path = new int[N];
for (int i = 0; i < N; i++) path[i] = -1;
path[0] = 0;
if (!hamiltonianCycleUtil(graph, path, 1)) {
cout << "\nCycle does not exist" << endl;
return false;
}
displaySolution(path);
return true;
}
void displaySolution(int path[]) {
cout << "Cycle Exists: Following is one Hamiltonian Cycle\n";
for (int i = 0; i < N; i++) cout << path[i] << " ";
cout << path[0] << endl;
}
int main() {
bool graph[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(graph);
return 0;
}
आउटपुट
Cycle Exists: Following is one Hamiltonian Cycle 0 4 1 2 3 0
