স্বাধীন সেট হল সমস্ত বাইনারি ট্রি নোডের সাবসেট যখন সেই সাবসেটের কোনো দুটি নোডের মধ্যে কোনো প্রান্ত থাকে না।
এখন উপাদানগুলির একটি সেট থেকে, আমরা দীর্ঘতম স্বাধীন সেটটি খুঁজে পাব। অর্থাত্ যদি উপাদানগুলিকে একটি বাইনারি ট্রি তৈরি করতে ব্যবহার করা হয়, তবে সমস্ত বৃহত্তম উপসেট, যেখানে সেই উপসেটের কোনও উপাদান একে অপরের সাথে সংযুক্ত থাকে না৷
ইনপুট এবং আউটপুট
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
