Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

सी++ प्रोग्राम बिना भारित ग्राफ में हैमिल्टनियन चक्र का पता लगाने के लिए

एक हैमिल्टनियन चक्र एक हैमिल्टनियन पथ है जैसे कि अंतिम शीर्ष से हैमिल्टनियन पथ के पहले शीर्ष तक एक किनारा (ग्राफ में) होता है। यह एक अप्रत्यक्ष ग्राफ़ में एक पथ है जो ग्राफ़ के प्रत्येक शीर्ष पर ठीक एक बार जाता है।

कार्य और उद्देश्य

Begin
   1. function isSafe() is used to check for whether it is
   adjacent to the previously added vertex and already not added.
   2. function hamiltonianCycle() solves the hamiltonian problem.
   3. function hamCycle() uses hamiltonianCycle() to solve
   the hamiltonian problem. It returns false if there is no
   Hamiltonian Cycle possible, otherwise return true and prints the path.
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 all vertices are included in Hamiltonian Cycle
   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)) { //Check if this vertex can be added to Hamiltonian Cycle
         path[pos] = n;
         //recur to construct rest of the path
         if (hamiltonianCycle (g, path, pos+1) == true)
            return true;
         path[pos] = -1; //remove vertex if it doesn’t lead to the solution
      }
   }
   return false;
}
bool hamCycle(bool g[N][N]) {
   int *path = new int[N];
   for (int i = 0; i < N; i++)
   path[i] = -1;
   //put vertex 0 as the first vertex in the path. If there is a Hamiltonian Cycle, then the path can be started from any point
   //of the cycle as the graph is undirected
   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

  1. कार्ड गेम के विजेता को खोजने के लिए C++ प्रोग्राम

    मान लीजिए कि हमारे पास क्रमशः k1 और k2 आकार की एक संख्या n, दो सरणियाँ A और B हैं। अमल और बिमलारे दिलचस्प कार्ड गेम खेल रहे हैं। n कार्ड हैं, जिनकी संख्या 1 से n है। प्रारंभ में कार्ड उनके बीच वितरित किए जाते हैं। खेल इस प्रकार है:प्रत्येक मोड़ पर, प्रत्येक खिलाड़ी अपना एक कार्ड (जो भी वे चाहते हैं)

  1. C++ प्रोग्राम चतुर्भुज की चौथी भुजा ज्ञात करने के लिए

    मान लीजिए कि हमारे पास तीन संख्याएँ a, b और c हैं। हम एक बंद बाड़ को मनमाने ढंग से गैर-पतित सरल चतुर्भुज के आकार में बनाना चाहते हैं। हमारे पास पहले से ही ए, बी और सी लंबाई के तीन पक्ष हैं। हमें दूसरा पक्ष d खोजना होगा। इसलिए, यदि इनपुट a =12 की तरह है; बी =34; c =56, तो आउटपुट 42 होगा, अन्य उत्तर

  1. C++ प्रोग्राम ग्राफ में सुपर वर्टिस का पता लगाने के लिए

    मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्ष हैं। कोने 1 से n तक गिने जाते हैं, और वे सरणी किनारों में दिए गए किनारों से जुड़े होते हैं। प्रत्येक शीर्ष का 1 से n तक की संख्या के भीतर x मान होता है जो कि सरणी मान में दिया जाता है। अब, हमें ग्राफ से अति शीर्षों का पता लगाना है। एक शीर्ष i को सु