C++でN分木を走査する方法の総数を求めるアルゴリズム

N分木（N-aryツリー）が与えられたとき、その木を走査できる方法が全部で何通りあるかを求める問題について解説します。例として以下のような木を考えてみましょう。

上記の木の場合、答えは 192 となります。

この問題を解くには、組み合わせ論に関する基礎知識が必要です。すべての経路について可能な順列の組み合わせを考慮することで、答えを求めることができます。

解法のアプローチ

このアプローチでは、レベル順走査（幅優先探索：BFS）を行いながら、各ノードが持つ子の数を調べます。そして、その子の数の階乗を答えに掛け合わせていくだけで計算できます。

あるノードに子が n 個ある場合、それらの子を訪問する順序は n! 通り存在します。したがって、全ノードについて階乗を掛け合わせたものが、木全体の走査方法の総数になります。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
struct Node{ // ノードの構造体
    char key;
    vector<Node *> child;
};
Node *createNode(int key){ // 新しいノードを初期化する関数
    Node *temp = new Node;
    temp->key = key;
    return temp;
}
long long fact(int n){ // 階乗を計算する関数
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}
int main(){
    Node *root = createNode('A');
    (root->child).push_back(createNode('B'));
    (root->child).push_back(createNode('F'));
    (root->child).push_back(createNode('D'));
    (root->child).push_back(createNode('E'));
    (root->child[2]->child).push_back(createNode('K'));
    (root->child[1]->child).push_back(createNode('J'));
    (root->child[3]->child).push_back(createNode('G'));
    (root->child[0]->child).push_back(createNode('C'));
    (root->child[2]->child).push_back(createNode('H'));
    (root->child[1]->child).push_back(createNode('I'));
    (root->child[2]->child[0]->child).push_back(createNode('N'));
    (root->child[2]->child[0]->child).push_back(createNode('M'));
    (root->child[1]->child[1]->child).push_back(createNode('L'));
    queue<Node*> q;
    q.push(root);
    long long ans = 1;
    while(!q.empty()){
        auto z = q.front();
        q.pop();
        ans *= fact(z -> child.size());
        cout << z->child.size() << " ";
        for(auto x : z -> child)
           q.push(x);
   }
   cout << ans << "\n";
   return 0;
}

出力結果

4 1 2 2 1 0 0 1 2 0 0 0 0 0 192

コードの解説

このプログラムでは、BFS（幅優先探索）によるレベル順走査を実行し、各ノードが持つ子の数を順番に確認しています。

• まず、キューにルートノードを追加します。
• キューからノードを取り出すたびに、その子の数の階乗を答え ans に掛け合わせます。
• 同時に、各子ノードをキューに追加して処理を続けます。

例えば、ルートノードには4つの子があるため 4! = 24、次のレベルのノードごとの貢献も同様に計算され、最終的に 24 × 2 × 2 × 2 × 2 = 192 という結果が得られます。

まとめ

本記事では、組み合わせ論の考え方とBFS（幅優先探索）を組み合わせることで、N分木を走査する方法の総数を効率的に求める手法を学びました。各ノードの子数の階乗を掛け合わせるというシンプルな発想で、O(N) の時間計算量で解ける点がポイントです。

同じロジックは C言語、Java、Python など他のプログラミング言語でも実装可能です。ぜひ参考にしてみてください。