C++에서 BFS를 사용하여 트리의 주어진 수준에서 노드 수를 계산합니다.

<시간/>

정점으로 트리의 노드를 포함하는 무방향 그래프가 주어집니다. 목표는 BFS(Breadth First Search) 알고리즘을 사용하여 트리의 주어진 수준에서 노드 수를 찾는 것입니다.

BFS 알고리즘:-

이 알고리즘은 그래프/트리 레벨을 레벨별로 탐색하기 시작합니다. 레벨 0의 노드에서 시작하여 먼저 레벨 1에서 직접 연결된 모든 노드를 순회한 다음 다음 레벨의 모든 노드를 순회하는 식으로 진행됩니다.

현재 수준에서 노드를 수평으로 순회합니다.
비슷한 방식으로 다음 수준에서 노드를 탐색합니다.

예를 들어 이해합시다.

예

입력 - 레벨=2

C++에서 BFS를 사용하여 트리의 주어진 수준에서 노드 수를 계산합니다.

출력 - BFS를 사용하는 트리에서 주어진 수준의 노드 수는 다음과 같습니다. 1

설명 - 위에 표시된 것처럼 모든 수준은 그래프에서 단일 노드를 갖습니다.

입력 - 레벨=1

C++에서 BFS를 사용하여 트리의 주어진 수준에서 노드 수를 계산합니다.

출력 - BFS를 사용하는 트리에서 주어진 수준의 노드 수는 다음과 같습니다. 2

설명 - 위에 표시된 것처럼 모든 수준은 그래프에서 단일 노드를 갖습니다. 노드는 1, 2입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서 우리는 각 노드를 순회하고 해당 수준을 부모보다 한 수준 더 높게 설정합니다. 인접 목록 표현을 사용하여 그래프를 표현합니다.

시작 노드가 0이면

레벨[0]=0,

레벨[1] =레벨[0]+1 =1, 레벨[2]=레벨[0]+1=1

레벨[3]=레벨[2]+1 =2, 레벨[4]=레벨[2]+1=2

C++에서 BFS를 사용하여 트리의 주어진 수준에서 노드 수를 계산합니다.

정점 수로 데이터를 사용하고 인접 목록에 대한 포인터로 다음 데이터를 사용하여 그래프를 나타내는 클래스 노드를 만듭니다.
공개 메소드 insert(int val, int point)는 그래프에 가장자리를 추가합니다.
point의 인접 목록에 val을 추가하고 val의 인접 목록을 가리킵니다.
count_nodes(int a, int b) 함수는 소스 노드 a에서 시작하는 b 수준의 노드 수를 반환합니다.
초기 개수를 0으로 설정합니다.
bool 배열 검사 =new bool[data]
배열 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에 추가합니다.
인접한 각 정점의 레벨을 a + 1의 레벨로 설정합니다.
while 루프가 끝날 때 for 루프와 for each 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