ปัญหาชุดอิสระที่ใหญ่ที่สุด

ชุดอิสระเป็นชุดย่อยของโหนดต้นไม้ไบนารีทั้งหมดเมื่อไม่มีขอบระหว่างสองโหนดในชุดย่อยนั้น

จากชุดขององค์ประกอบ เราจะพบชุดอิสระที่ยาวที่สุด กล่าวคือ หากองค์ประกอบถูกใช้เพื่อสร้างไบนารีทรี ชุดย่อยที่ใหญ่ที่สุดทั้งหมด โดยที่ไม่มีองค์ประกอบในชุดย่อยนั้นเชื่อมต่อถึงกัน

อินพุตและเอาต์พุต

Input:
A binary tree.

Output:
Size of the Largest Independent Set is: 5

อัลกอริทึม

longSetSize(root)

ในอัลกอริทึมนี้ Binary tree จะถูกสร้างขึ้น แต่ละโหนดของ tree นั้นจะเก็บข้อมูลและ setSize

อินพุต - โหนดรูทของไบนารีทรี

ผลลัพธ์ − ขนาดของชุดที่ยาวที่สุด

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