Đặt vấn đề độc lập lớn nhất

Tập hợp Độc lập là tập hợp con của tất cả các nút cây nhị phân khi không có cạnh nào giữa hai nút bất kỳ trong tập hợp con đó.

Bây giờ từ một tập hợp các phần tử, chúng ta sẽ tìm ra tập độc lập dài nhất. tức là nếu các phần tử được sử dụng để tạo thành cây nhị phân, thì tất cả các tập hợp con lớn nhất, trong đó không có phần tử nào trong tập hợp con đó được kết nối với nhau.

Đầu vào và Đầu ra

Input:
A binary tree.

Output:
Size of the Largest Independent Set is: 5

Thuật toán

longSetSize(root)

Trong thuật toán này, cây nhị phân sẽ được hình thành, mỗi nút của cây đó sẽ chứa dữ liệu và setSize.

Đầu vào - Nút gốc của cây nhị phân.

Đầu ra - Kích thước của tập hợp dài nhất.

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

Ví dụ

#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);
}

Đầu ra

Size of the Largest Independent Set is − 5