C++で木構造の全ノードに情報を伝播させるための最小反復回数を求める方法

本記事では、n個のノードからなる木構造(ツリー)データ構造が与えられたとき、根ノード(root)からすべてのノードへ情報を行き渡らせるために必要な最小反復回数を求めるアルゴリズムを解説します。

与えられる木には根ノードがあり、各ノードは任意の数の子を持つことができます。ここで重要なルールは、1回の反復につき、あるノードはその子のうち1つにのみ情報を伝えられるという点です。ただし、子ノードがさらにその子へ情報を渡している間も、根ノードは別の子へ情報を渡し続けることができます。この並行性を考慮して、全ノードへの伝達完了までに必要な最小回数を計算します。

入出力シナリオの例

例1:

• 入力: 根とその他のノードを含め合計11ノードからなる木
• 出力: 木の中の全ノードに情報を渡すための最小反復回数: 5

説明: 根ノード0は、多くの子を持つノード1に最初にデータを渡します。その後、ノード4、ノード3、ノード6の順に渡し、最後にノード2へ渡します。したがって、合計で5回の反復が必要となります。ポイントは、子の多い部分木から優先的に情報を渡すことで、全体の所要時間を最小化できることです。

例2:

• 入力: 根と1つの子ノード、合計2ノードからなる木
• 出力: 最小反復回数: 1

説明: 根ノードに子が1つしか存在しないため、情報伝達に必要な反復回数は1回だけで済みます。

アルゴリズムのアプローチ

この問題を解く基本的な考え方は以下の通りです。

• 木を構築するクラスを作成し、ノード数をデータメンバとして持ち、子リスト用のポインタ List_children を定義します。また、privateメソッドとして void Iteration(int vertices, int arr[]) を宣言します。さらに、引数付きコンストラクタ Tree(int nodes)、メソッド void insert_node(int a, int b)、int Min_Iteration()、static int check(const void *a_1, const void *b_1) を宣言します。
• コンストラクタ Tree::Tree(int nodes): メンバ変数 nodes を設定し、List_children に new list[nodes] を割り当てます。
• Tree::insert_node(int a, int b): List_children[a] に対して push_back(b) を呼び出し、親aに子bを追加します。
• Tree::Iteration(int vertices, int arr[])(再帰的な核心部分):
  • arr[vertices] に子の数(List_children[vertices].size())を設定します。
  • *ptr に new int[arr[vertices]] を割り当てます。
  • temp と temp_2 を 0 で初期化します。
  • イテレータ list::iterator it を宣言します。
  • List_children[vertices] の先頭から末尾までループを回し、各子に対して Iteration(*it, arr) を再帰呼び出しし、結果 arr[*it] を ptr[temp++] に格納します。
  • qsort(ptr, arr[vertices], sizeof(int), check) によりクイックソートを実行します。
  • 再度ループを回し、temp_2 = ptr[temp] + temp + 1 を計算し、arr[vertices] = max(arr[vertices], temp_2) で最大値を更新します。最後に delete[] ptr でメモリを解放します。
• Tree::Min_Iteration():
  • int *ptr = new int[nodes] を宣言し、変数 temp を -1 で初期化します。
  • 全要素 ptr[i] を 0 で初期化します。
  • Iteration(0, ptr) を呼び出し、temp に ptr[0] を代入して delete[] ptr で解放します。
  • temp を返します。
• Tree::check(const void *a_1, const void *b_1): ソート用の比較関数で、(*(int*)b_1 - *(int*)a_1) の降順比較結果を返します。
• main()関数内: 引数付きコンストラクタで木オブジェクトを生成し、insert_node() メソッドでノードを挿入した後、Min_Iteration() を呼び出して最小反復回数を計算・表示します。

実装例(C++コード)

#include<bits/stdc++.h>
using namespace std;

class Tree
{
    int nodes;
    list<int> *List_children;
    void Iteration(int vertices, int arr[]);

public:
    //クラスのコンストラクタ
    Tree(int nodes);
    //木にノードを挿入するメソッド
    void insert_node(int a, int b);
    //最小反復回数を計算するメソッド
    int Min_Iteration();
    static int check(const void *a_1, const void *b_1);
};

Tree::Tree(int nodes)
{
    this->nodes = nodes;
    List_children = new list<int>[nodes];
}
void Tree::insert_node(int a, int b)
{
    List_children[a].push_back(b);
}
void Tree::Iteration(int vertices, int arr[])
{
    arr[vertices] = List_children[vertices].size();
    int *ptr = new int[arr[vertices]];
    int temp = 0;
    int temp_2 = 0;
    list<int>::iterator it;

    for(it = List_children[vertices].begin(); it!= List_children[vertices].end(); ++it)
    {
        Iteration(*it, arr);
        ptr[temp++] = arr[*it];
    }

    qsort(ptr, arr[vertices], sizeof(int), check);

    for(temp = 0; temp < List_children[vertices].size(); temp++)
    {
        temp_2 = ptr[temp] + temp + 1;
        arr[vertices] = max(arr[vertices], temp_2);
    }
    delete[] ptr;
}
int Tree::Min_Iteration()
{
    int *ptr = new int[nodes];
    int temp = -1;

    for (int i = 0; i < nodes; i++)
    {
        ptr[i] = 0;
    }
    Iteration(0, ptr);
    temp = ptr[0];
    delete[] ptr;
    return temp;
}
int Tree::check(const void * a_1, const void * b_1)
{
    int result = ( *(int*)b_1 - *(int*)a_1 );
    return result;
}
int main()
{
    Tree T_1(8);
    T_1.insert_node(0, 1);
    T_1.insert_node(0, 3);
    T_1.insert_node(0, 4);
    T_1.insert_node(0, 6);
    T_1.insert_node(0, 2);
    T_1.insert_node(1, 7);
    T_1.insert_node(1, 2);
    T_1.insert_node(1, 3);
    T_1.insert_node(4, 6);
    T_1.insert_node(4, 7);
    cout<<"Minimum no. of iterations to pass information to all nodes in the tree are:"<<T_1.Min_Iteration();

    Tree T_2(2);
    T_2.insert_node(0, 1);
    cout<<"\nMinimum no. of iterations to pass information to all nodes in the tree are:" <<T_2.Min_Iteration();

    return 0;
}

出力結果

上記のコードを実行すると、次のような出力が得られます。

Minimum no. of iterations to pass information to all nodes in the tree are: 8
Minimum no. of iterations to pass information to all nodes in the tree are: 1

まとめ

このアルゴリズムの肝となるのは、「子の部分木が大きいノードから順に情報を渡す」という貪欲法(Greedy法)です。各ノードでは、その子孫の部分木ごとに必要な時間を再帰的に求め、降順にソートした上で、「i番目に渡す子の所要時間 + i」の最大値を取ることで、並行伝播を考慮した最小反復回数を導き出しています。これにより、木構造全体への効率的な情報伝播戦略をO(n log n)程度の計算量で実現できます。