資料結構
網路
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 次瀏覽
廣告