数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究最大独立集问题
独立集是所有二叉树节点的子集，其中子集中的任意两个节点之间都没有边。
现在从一组元素中，我们将找出最长的独立集。即如果元素用于形成二叉树，则所有最大子集，其中该子集中的元素都互不连接。
输入和输出
Input: A binary tree.Output: Size of the Largest Independent Set is: 5
算法
longSetSize(root)
在此算法中，将形成二叉树，该树的每个节点将保存数据和 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
更新时间：16-Jun-2020
334 次浏览
广告