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

C++ में अनडायरेक्टेड ग्राफ में दिए गए आकार का इंडिपेंडेंट सेट मौजूद है या नहीं खोजें


अवधारणा

एक दिए गए अनडायरेक्टेड ग्राफ के संबंध में, सत्यापित करें कि क्या इसमें आकार l का एक इंडिपेंडेंट सेट है। यदि आकार l का एक इंडिपेंडेंट सेट मौजूद है तो 'Yes' प्रिंट करें, अन्यथा 'No' प्रिंट करें। यह ध्यान दिया जाना चाहिए कि एक ग्राफ में इंडिपेंडेंट सेट को उन शीर्षों के समूह के रूप में परिभाषित किया गया है जो एक-दूसरे से सीधे जुड़े नहीं हैं।

इनपुट

L = 4, graph = [[1, 0, 1, 0, 0], [0, 1, 1, 0, 0],[1, 1, 1, 1, 1], [0, 0, 1, 1, 0],[0, 0, 1, 0, 1]];

आउटपुट

Yes

C++ में अनडायरेक्टेड ग्राफ में दिए गए आकार का इंडिपेंडेंट सेट मौजूद है या नहीं खोजें

उपरोक्त ग्राफ में आकार 4 का एक इंडिपेंडेंट सेट है (शीर्ष 0, 1, 3, 4 एक-दूसरे से सीधे जुड़े नहीं हैं)। इसलिए आउटपुट 'Yes' है।

इनपुट

L = 4, graph =[[1, 1, 1, 0, 0],[1, 1, 1, 0, 0],[1, 1, 1, 1, 1],[0, 0, 1, 1, 0],[0, 0, 1, 0, 1]];

आउटपुट

No

C++ में अनडायरेक्टेड ग्राफ में दिए गए आकार का इंडिपेंडेंट सेट मौजूद है या नहीं खोजें

आरेख में, उपरोक्त ग्राफ में आकार 4 का इंडिपेंडेंट सेट नहीं है। इसलिए आउटपुट 'No' है।

विधि

<उल क्लास="सूची"><ली>सबसे पहले, sol नामक एक वेरिएबल को बूलियन False मान के साथ इनिशियलाइज़ करें।<ली>दिए गए ग्राफ से आकार L के शीर्षों के सभी संभावित सेट निर्धारित करें।<ली>यह देखा गया है कि यदि आकार l का एक इंडिपेंडेंट सेट मिलता है, तो sol का मान True में बदलें और लौटें।<ली>अन्यथा अन्य संभावित सेट्स के लिए जांच जारी रखें।<ली>अंत में, यदि sol True है, तो 'Yes' प्रिंट करें अन्यथा 'No' प्रिंट करें।

उदाहरण

<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// C++ code to check if a given graph // contains an independent set of size k #include <bits/stdc++.h> using namespace std; // फ़ंक्शन प्रोटोटाइप दिखाता है bool check1(int[][5], vector<int>&, int); // दिए गए आकार l का एक सेट बनाने वाला फ़ंक्शन bool func(int graph1[][5], vector<int>&arr1, int l, int index1, bool sol1[]){    // सत्यापित करें कि चयनित सेट इंडिपेंडेंट है या नहीं।    // sol के मान को True में बदलने और लौटने के लिए उपयोग किया जाता है    // यदि यह इंडिपेंडेंट है       if (l == 0){          if (check1(graph1, arr1, arr1.size())){             sol1[0] = true;             return true;          }       }       else{          // अब आकार l का सेट बनाया जा सकता है भले ही हम          // वर्तमान इंडेक्स पर शीर्ष को शामिल न करें।          if (index1 >= l){             vector<int> newvec(arr1.begin(), arr1.end());             newvec.push_back(index1);             return (func(graph1, newvec, l - 1,             index1 - 1, sol1) or             func(graph1, arr1, l, index1 - 1, sol1));          }             // अब आकार l का सेट नहीं बनाया जा सकता यदि हम          // वर्तमान इंडेक्स पर शीर्ष को शामिल न करें।          else{             arr1.push_back(index1);             return func(graph1, arr1, l - 1,             index1 - 1, sol1);          }       }    }    // दिए गए सेट को सत्यापित करने वाला फ़ंक्शन कि यह    // इंडिपेंडेंट है या नहीं    // arr --> आकार l का सेट (शामिल शीर्ष का    // इंडेक्स रखता है)    bool check1(int graph1[][5], vector<int>&arr1, int n1){       // सत्यापित करें कि प्रत्येक शीर्ष सेट में किसी अन्य          // शीर्ष से जुड़ा है या नहीं       for (int i = 0; i < n1; i++)          for (int j = i + 1; j < n1; j++)             if (graph1[arr1[i]][arr1[j]] == 1)             return false;       return true; } // ड्राइवर कोड int main(){    int graph1[][5] = {{1, 0, 1, 0, 0},{0, 1, 1, 0, 0},{1, 1, 1, 1, 1},{0, 0, 1, 1, 0},       {0, 0, 1, 0, 1}};       int l = 4;       vector<int> arr1; // खाली सेट       bool sol1[] = {false};       int n1 = sizeof(graph1) /       sizeof(graph1[0]);       func(graph1, arr1, l, n1 - 1, sol1);       if (sol1[0])          cout << "Yes" << endl;       else          cout << "No" << endl;       return 0; }

आउटपुट

Yes

  1. C++ प्रोग्राम: जांचें कि अनिर्देशित ग्राफ (Undirected Graph) में यूलरियन पथ है या नहीं C++ प्रोग्राम: जांचें कि अनिर्देशित ग्राफ (Undirected Graph) में यूलरियन पथ है या नहीं

    यूलर पथ एक ऐसा पथ है जिसके द्वारा हम प्रत्येक नोड को ठीक एक बार विजिट कर सकते हैं। हम समान एज का उपयोग कई बार कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक वर्टेक्स उस पथ के अंतिम वर्टेक्स से भी जुड़ा होता है। यूलर पथ का पता लगाने के लिए, हमें इन शर्तों का पालन कर

  1. C++ प्रोग्राम: जांचें कि अनिर्देशित ग्राफ में यूलरियन साइकिल है या नहीं C++ प्रोग्राम: जांचें कि अनिर्देशित ग्राफ में यूलरियन साइकिल है या नहीं

    यूलर सर्किट के बारे में जानने के लिए, हमें यूलर पथ के बारे में पता होना चाहिए। यूलर पथ एक ऐसा पथ है जिसके द्वारा हम प्रत्येक नोड को ठीक एक बार विजिट कर सकते हैं। हम समान एज का उपयोग कई बार कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक वर्टेक्स उस पथ के अंतिम वर्टेक

  1. Python में अनिर्देशित ग्राफ में दिए गए आकार का स्वतंत्र सेट है या नहीं जांचना Python में अनिर्देशित ग्राफ में दिए गए आकार का स्वतंत्र सेट है या नहीं जांचना

    मान लीजिए हमारे पास एक दिया गया अनिर्देशित ग्राफ है; हमें जांचना है कि क्या इसमें आकार l का एक स्वतंत्र सेट है। यदि आकार l का कोई स्वतंत्र सेट है तो Yes वापस करें अन्यथा No। हमें इस बात का ध्यान रखना है कि एक ग्राफ में स्वतंत्र सेट को उन शीर्षों के समूह के रूप में परिभाषित किया गया है जो सीधे एक-दूस