IndependentSet独立集问题

和独立集相关的一些图论的概念如下&＃xff1a;

• Independent Set 独立集问题
• Bipartite Graph 二分图
• Dominant Set 主导集
• Cycle Graph循环图

问题&＃xff1a;给你一个二叉树&＃xff0c;求出该二叉树的最大独立集。

思路&＃xff1a;二叉树问题可以用递归的办法来解决&＃xff0c;这个也不例外。更好的是&＃xff0c;这个问题还可以用动态规划的方法来解决。

设二叉树的根节点是root&＃xff0c;那么&＃xff0c;此二叉树的最大独立集要么包含root&＃xff0c;要么不包含root。所以&＃xff0c;最大独立集的大小 LISS (root) &＃61;&＃61; max( is_LISS(root), not_LISS(root) ).

使用递归的方法&＃xff0c;代码如下&＃xff1a;

#include
using namespace std;struct Node{int value;int is_LISS; // used in the dynamic programming version// the size of LIS when this is a member of the LISint not_LISS; // used in the dynamic programming version// the size of LIS when this is not a member of the LISNode* lchild;Node* rchild;Node(int val, int is_, int not_, Node* lch, Node* rch):value(val), is_LISS(is_), not_LISS(not_),lchild(lch), rchild(rch) {}
};int is_LISS(Node* root); // return the size of LIS when root is a member of the LIS
int not_LISS(Node* root); // return the size of LIS when root is not a member of the LISint is_LISS(Node* root)
{if(root&＃61;&＃61;NULL)return 0;elsereturn 1 &＃43; not_LISS(root->lchild) &＃43; not_LISS(root->rchild);
}int not_LISS(Node* root)
{if(root&＃61;&＃61;NULL)return 0;elsereturn max(is_LISS(root->lchild), not_LISS(root->lchild)) &＃43;max(is_LISS(root->rchild), not_LISS(root->rchild));
}// return the size of LIS of the tree rooted at root
int LISS(Node* root)
{return max(is_LISS(root), not_LISS(root));
}int main(int argc, char** argv)
{Node* n70 &＃61; new Node(70,-1,-1,NULL,NULL);Node* n80 &＃61; new Node(80,-1,-1,NULL,NULL);Node* n50 &＃61; new Node(50,-1,-1,n70,n80);Node* n40 &＃61; new Node(40,-1,-1,NULL,NULL);Node* n20 &＃61; new Node(20,-1,-1,n40,n50);Node* n60 &＃61; new Node(60,-1,-1,NULL,NULL);Node* n30 &＃61; new Node(30,-1,-1,NULL,n60);Node* n10 &＃61; new Node(10,-1,-1,n20,n30);cout<}


上面的程序构造了一棵如下图所示的二叉树&＃xff0c;求出的LISS是5. 只要把is_LISS函数和not_LISS函数改一下&＃xff0c;在把每次得到的函数返回值保存在每个节点的is_LISS和not_LISS成员中&＃xff0c;这样&＃xff0c;就可以免去每次递归调用&＃xff0c;而是直接检查is_LISS和not_LISS是否已经求得&＃xff08;如果是-1&＃xff0c;说明还没求得&＃xff09;。这样就可用得到动态规划版的最大对立集问题求解。