सबसे बड़ा इंडिपेंडेंट सेट समस्या

इंडिपेंडेंट सेट सभी बाइनरी ट्री नोड्स का सबसेट है जब उस सबसेट में किन्हीं दो नोड्स के बीच कोई एज नहीं होता।

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

इनपुट और आउटपुट

इनपुट: एक बाइनरी ट्री।
आउटपुट: सबसे बड़े इंडिपेंडेंट सेट का आकार है: 5

एल्गोरिदम

longSetSize(root)

इस एल्गोरिदम में बाइनरी ट्री बनेगा, उस ट्री का प्रत्येक नोड डेटा और setSize रखेगा।

इनपुट: बाइनरी ट्री का रूट नोड।
आउटपुट: सबसे लंबे सेट का आकार।

शुरुआत
    यदि root = φ, तो
        वापस 0
    यदि setSize(root) ≠ 0, तो
        वापस setSize(root)
    यदि root का कोई बच्चा नहीं है, तो
        setSize(root) := 1
        वापस setSize(root)
    setSizeEx := longSetSize(left(root)) + longSetSize(right(root)) // रूट को छोड़कर
    setSizeIn := 1
    यदि बायां बच्चा मौजूद है, तो
        setSizeIn := setSizeIn + longSetSize(left(left(root))) + longSetSize(left(right(root)))
    यदि दायां बच्चा मौजूद है, तो
        setSizeIn := setSizeIn + longSetSize(right(left(root))) + longSetSize(right(right(root)))
    यदि setSizeIn > setSizeEx, तो
        setSize(root) := setSizeIn
    अन्यथा
        setSize(root) := setSizeEx
    वापस setSize(root)
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

struct node {
    int data;
    int setSize;
    node *left, *right;
};

int longSetSize(node *root) {
    if (root == NULL)
        return 0;
    if (root->setSize != 0)
        return root->setSize;
    if (root->left == NULL && root->right == NULL)
        return (root->setSize = 1);
    
    int setSizeEx = longSetSize(root->left) + longSetSize(root->right);
    int setSizeIn = 1;
    
    if (root->left)
        setSizeIn += longSetSize(root->left->left) + longSetSize(root->left->right);
    if (root->right)
        setSizeIn += longSetSize(root->right->left) + longSetSize(root->right->right);
    
    root->setSize = (setSizeIn > setSizeEx) ? setSizeIn : setSizeEx;
    return root->setSize;
}

struct node* getNode(int data) {
    node* newNode = new node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->setSize = 0;
    return newNode;
}

int main() {
    node *root = getNode(20);
    root->left = getNode(8);
    root->left->left = getNode(4);
    root->left->right = getNode(12);
    root->left->right->left = getNode(10);
    root->left->right->right = getNode(14);
    root->right = getNode(22);
    root->right->right = getNode(25);
    cout << "Size of the Largest Independent Set is: " << longSetSize(root);
}

आउटपुट

Size of the Largest Independent Set is: 5