C ++でBFSを使用して、ツリー内の特定のレベルのノードの数をカウントします

ツリーのノードを頂点として含む無向グラフが与えられます。目標は、BFS（幅優先探索）アルゴリズムを使用して、ツリーの特定のレベルでノードの数を見つけることです。

BFSアルゴリズム：-

このアルゴリズムは、レベルごとにグラフ/ツリーのトラバースを開始します。レベル0のノードから開始して、最初にレベル1でノードに直接接続されているすべてのノードをトラバースし、次に次のレベルのすべてのノードをトラバースします。

• 現在のレベルでノードを水平方向にトラバースします。
• 同様の方法で次のレベルのノードをトラバースします。

例を挙げて理解しましょう。

例

入力- level =2

出力- BFSを使用したツリー内の特定のレベルのノード数は次のとおりです。1

説明- 上に示したように、すべてのレベルのグラフに単一のノードがあります。

入力- level =1

出力- BFSを使用したツリー内の特定のレベルのノード数は次のとおりです。2

説明- 上に示したように、すべてのレベルのグラフに単一のノードがあります。ノードは1、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

• 頂点の数としてデータを使用し、隣接リストへのポインタとして次のデータを使用して、グラフを表すクラスノードを作成します。
• パブリックメソッドinsert（int val、int point）は、グラフにエッジを追加します。
• ポイントの隣接リストにvalを追加し、valの隣接リストをポイントします。
• 関数count_nodes（int a、int b）は、ソースノードaから始まるレベルbのノードの数を返します。
• 初期カウントを0に設定します。
• bool array check =newbool[data]を実行します。
• Array arr [data]は、グラフの各頂点のレベルを格納します。
• forループを使用して、グラフのすべての頂点を非訪問として設定し、check [i]=falseおよびarr[i]=0に設定します。
• BFSトラバーサル用のキューl1を作成します。
• 開始した頂点をcheck[a]=trueとしてマークし、l1.push_back（a）を使用してl1に追加し、そのレベルを0に設定します。arr[a]=0。
• キューl1が空ではない間。
• 前の要素をa=l1とします。 front（）を使用して、l1.pop_front（）を使用して出力します。
• の隣接するすべての未訪問の頂点を訪問済みとしてマークし、キューl1に追加します。
• 隣接する各頂点のレベルを+1のレベルとして設定します。
• whileループの最後に、forループと各arr [i]==b増分カウントを使用してarr[]をトラバースします。
• 結果としての最終返品カウント

例

#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