C++でBFS（幅優先探索）を使って木構造の指定レベルにあるノード数を数える方法

木構造のノードを頂点として含む無向グラフが与えられたとき、BFS（幅優先探索）アルゴリズムを用いて、指定されたレベルに存在するノードの数を求めるのが本記事の目的です。

BFSアルゴリズムとは

BFSは、グラフや木をレベル（階層）ごとに走査していくアルゴリズムです。レベル0のノードから探索を開始し、まずそのノードに直接接続されているレベル1のすべてのノードを訪問し、続いて次のレベルのノードを順番に走査していきます。

• 現在のレベルのノードを横方向（同じ階層内）に走査する。
• 同様の手順で、次のレベルのノードを走査する。

具体例で理解しよう

例1：

入力：level = 2

出力：BFSを用いて指定レベルのノード数をカウントした結果：1

解説：上図のように、各レベルにはノードが1つずつしか存在しないため、レベル2のノード数は1となります。

例2：

入力：level = 1

出力：BFSを用いて指定レベルのノード数をカウントした結果：2

解説：上図において、レベル1に存在するノードは「1」と「2」の2つです。

プログラムで使用するアプローチ

このアプローチでは、各ノードを走査しながら、そのノードのレベルを「親ノードのレベル + 1」として設定していきます。グラフは隣接リスト形式で表現します。

例えば、開始ノードが0の場合、各ノードのレベルは以下のように決まります。

• level[0] = 0
• level[1] = level[0] + 1 = 1、level[2] = level[0] + 1 = 1
• level[3] = level[2] + 1 = 2、level[4] = level[2] + 1 = 2

処理の手順

• 頂点数を保持するデータメンバーと、隣接リストへのポインタを持つクラス「node」を作成する。
• 公開メソッド insert(int val, int point) は、グラフに辺を追加する。具体的には、val を point の隣接リストに、point を val の隣接リストにそれぞれ追加する（無向グラフのため双方向に登録）。
• 関数 count_nodes(int a, int b) は、始点ノード a から見てレベル b に存在するノードの数を返す。
• カウント変数 count を 0 で初期化する。
• 訪問状態を管理する bool 型配列 check = new bool[data] を用意する。
• 配列 arr[data] には、グラフの各頂点のレベルを格納する。
• forループを使ってすべての頂点を「未訪問」かつ「レベル0」の状態に初期化する（check[i] = false、arr[i] = 0）。
• BFS走査用のキュー l1 を作成する。
• 始点頂点 a を訪問済みとしてマークし（check[a] = true）、l1.push_back(a) でキューに追加し、そのレベルを arr[a] = 0 と設定する。
• キュー l1 が空でない間、以下を繰り返す。
• 先頭要素を a = l1.front() で取得し、l1.pop_front() で取り除く。
• a に隣接する未訪問の頂点をすべて訪問済みとしてマークし、キュー l1 に追加する。
• 各隣接頂点のレベルを「a のレベル + 1」に設定する。
• whileループ終了後、forループで arr[] を走査し、arr[i] == b となる要素があれば count をインクリメントする。
• 最後に count を結果として返す。

C++実装コード

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

class node {
    int data;
    list < int > * next;
    public:
        node(int data) {
            this -> data = data;
            next = new list < int > [data];
        }
    void insert(int val, int point) {
        next[val].push_back(point);
        next[point].push_back(val);
    }
    int count_nodes(int a, int b);
};

int node::count_nodes(int a, int b) {
    int count = 0;
    bool * check = new bool[data];
    int arr[data];

    for (int i = 0; i < data; i++) {
        check[i] = false;
        arr[i] = 0;
    }

    list < int > l1;
    check[a] = true;
    l1.push_back(a);
    arr[a] = 0;

    while (!l1.empty()) {
        a = l1.front();
        l1.pop_front();
        for (auto it = next[a].begin(); it != next[a].end(); ++it) {
            if (!check[ * it]) {
                arr[ * it] = arr[a] + 1;
                check[ * it] = true;
                l1.push_back( * it);
            }
        }
    }
    for (int i = 0; i < data; i++) {
        if (arr[i] == b) {
            count++;
        }
    }
    return count;
}
int main() {
    node n1(5);
    n1.insert(1, 2);
    n1.insert(0, 3);
    n1.insert(1, 3);
    n1.insert(2, 4);

    int level = 1;

    cout << "Count of number of nodes at given level in a tree using BFS are: " << n1.count_nodes(0, level);
    return 0;
}

上記のコードを実行すると、以下の出力が得られます。

実行結果

Count of number of nodes at given level in a tree using BFS are: 1

このように、BFSを活用することで、木構造やグラフの任意のレベルに存在するノード数を効率的に求めることができます。計算量は頂点数をV、辺数をEとすると O(V + E) となり、大規模なグラフに対しても実用的な手法です。