二分木の最大独立集合問題：動的計画法による解法とC++実装例

独立集合とは

独立集合（Independent Set）とは、二分木のノードから選んだ部分集合のうち、その部分集合に含まれるどの2つのノード間にも辺が存在しないものを指します。

本記事では、与えられた要素の集合から最大の独立集合を見つける方法を解説します。つまり、要素を使って二分木を構築した場合に、互いに接続されていない要素のみからなる最大の部分集合を求めるという問題です。

入力と出力

入力：二分木

出力：
最大の独立集合のサイズは 5

アルゴリズム

longSetSize(root)

このアルゴリズムでは二分木を構築し、各ノードが「データ（data）」と「集合サイズ（setSize）」の2つの情報を保持します。

入力 − 二分木のルートノード

出力 − 最長の集合のサイズ

Begin
　if root = φ, then
　　return 0
　if setSize(root) ≠ 0, then
　　return setSize(root)
　if root has no child, then
　　setSize(root) := 1
　　return setSize(root)
　setSizeEx := longSetSize(left(root)) + longSetSize(right(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

アルゴリズムのポイント

この問題を効率的に解く鍵となるのは動的計画法（メモ化）です。各ノードについて、次の2つの選択肢を比較します。

• ノードを含む場合：直接の子ノードは含められないため、代わりに孫ノード以降の部分問題の解を加算します。
• ノードを含まない場合：左右の子部分木それぞれの独立集合のサイズをそのまま合計できます。

計算結果を各ノードの setSize に保存しておくことで、同じ部分問題を繰り返し計算する無駄を省けます。これにより、全ノードを一度ずつ処理するだけでよく、O(n) の計算量で答えを求めることができます。

C++による実装例

#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)  // 子ノードがない場合
        return (root->setSize = 1);

    // ルートを含まない場合のサイズ = 左部分木のサイズ + 右部分木のサイズ
    int setSizeEx = longSetSize(root->left) + longSetSize(root->right);
    int setSizeIn = 1;                   // ルート自身を含む場合

    if (root->left)                      // 左部分木が存在する場合
        setSizeIn += longSetSize(root->left->left) + longSetSize(root->left->right);

    if (root->right)                     // 右部分木が存在する場合
        setSizeIn += longSetSize(root->right->left) + longSetSize(root->right->right);

    root->setSize = (setSizeIn > setSizeEx) ? setSizeIn : setSizeEx;

    return root->setSize;
}

struct node* getNode(int 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