सबसे बड़ी स्वतंत्र सेट समस्या

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

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

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

Input:
A binary tree.

Output:
Size of the Largest Independent Set is: 5

एल्गोरिदम

longSetSize(root)

इस एल्गोरिथम में बाइनरी ट्री बनेगा, उस ट्री का हर नोड डेटा और सेटसाइज को होल्ड करेगा।

इनपुट - बाइनरी ट्री का रूट नोड.

आउटपुट - सबसे लंबे सेट का आकार.

Begin
   if root = φ, then
      return 0
   if setSize(root) ≠ 0, then
      setSize(root)
   if root has no child, then
      setSize(root) := 1
      return setSize(root)
   setSizeEx := longSetSize(left(root)) + longSetSize(right(root)) //excluding root
   setSizeIn := 1

   if left child exists, then
      setSizeIn := setSizeIn + longSetSize(left(left(root))) + longSetSize(left(right(root)))

   if right child exists, then
      setSizeIn := setSizeIn + longSetSize(right(left(root))) + longSetSize(right(right(root)))

   if setSizeIn > setSizeEx, then
      setSize(root) := setSizeIn
   else
      setSize(root) := setSizeEx

   return setSize(root)
End

उदाहरण

#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)    //when there is no child
      return (root->setSize = 1);

   // set size exclusive root is set size of left and set size of right

   int setSizeEx = longSetSize(root->left) + longSetSize(root->right);
   int setSizeIn = 1;             //inclusive root node

   if (root->left)               //if left sub tree is present
      setSizeIn += longSetSize(root->left->left) + longSetSize(root->left->right);

   if (root->right)                //if right sub tree is present
      setSizeIn += longSetSize(root->right->left) +longSetSize(root->right->right);
   root->setSize = (setSizeIn>setSizeEx)?setSizeIn:setSizeEx;

   return root->setSize;
}

struct node* getNode(int data) {          //create a new node with given 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