นับจำนวนโหนดที่ระดับที่กำหนดในทรีโดยใช้ BFS ใน C++

กำหนดกราฟแบบไม่มีทิศทางที่มีโหนดของต้นไม้เป็นยอด เป้าหมายคือการค้นหาจำนวนโหนดที่ระดับที่กำหนดของทรีโดยใช้อัลกอริธึม BFS (การค้นหาแรกแบบกว้าง)

อัลกอริทึม BFS:-

อัลกอริธึมนี้เริ่มสำรวจกราฟ/ระดับต้นไม้ตามระดับ เริ่มจากโหนดที่ระดับ 0 ขั้นแรก จะข้ามโหนดทั้งหมดที่เชื่อมต่อโดยตรงกับมันที่ระดับ 1 จากนั้นจะข้ามโหนดทั้งหมดที่ระดับถัดไปเป็นต้น

• ข้ามโหนดในแนวนอนที่ระดับปัจจุบัน
• ข้ามโหนดที่ระดับถัดไปในลักษณะที่คล้ายกัน

ให้เราเข้าใจด้วยตัวอย่าง

ตัวอย่าง

ป้อนข้อมูล - ระดับ=2

ผลลัพธ์ - จำนวนโหนดที่ระดับที่กำหนดในทรีโดยใช้ BFS คือ:1

คำอธิบาย - ดังที่แสดงไว้ข้างต้น ทุกระดับมีโหนดเดียวในกราฟ

ป้อนข้อมูล - ระดับ=1

ผลลัพธ์ - จำนวนโหนดที่ระดับที่กำหนดในทรีโดยใช้ BFS คือ:2

คำอธิบาย - ดังที่แสดงไว้ข้างต้น ทุกระดับมีโหนดเดียวในกราฟ โหนดคือ 1, 2

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราจะสำรวจแต่ละโหนดและตั้งค่าระดับเป็นระดับที่มากกว่าระดับบนสุดหนึ่งระดับ เราจะแสดงกราฟโดยใช้การแสดงรายการที่อยู่ติดกัน

หากโหนดเริ่มต้นเป็น 0 ดังนั้น

ระดับ[0]=0,

ระดับ[1] =ระดับ[0]+1 =1, ระดับ[2]=ระดับ[0]+1=1

ระดับ[3]=ระดับ[2]+1 =2, ระดับ[4]=ระดับ[2]+1=2

• สร้างโหนดคลาสที่แสดงกราฟที่มีข้อมูลเป็นจำนวนจุดยอดและถัดไปเป็นตัวชี้ไปยังรายการที่อยู่ติดกัน
• การแทรกวิธีสาธารณะ (int val, int point) เพิ่มขอบให้กับกราฟ
• เพิ่มรายการที่อยู่ติดกันของ val to point และชี้ไปที่รายการที่อยู่ติดกันของ val
• Function count_nodes(int a, int b) คืนค่าจำนวนโหนดที่ระดับ b โดยเริ่มจากโหนดต้นทาง a.
• ตั้งค่าการนับเริ่มต้นเป็น 0
• ตรวจสอบบูลอาเรย์ =บูลใหม่[ข้อมูล].
• Array arr[data] เก็บระดับของแต่ละจุดยอดของกราฟ
• ตั้งค่าจุดยอดทั้งหมดของกราฟเป็นไม่มีการไปเยี่ยมชมโดยใช้ for loop และตั้งค่า check[i] =false และ arr[i] =0
• สร้างคิว l1 สำหรับการข้ามผ่าน BFS
• ทำเครื่องหมายว่าจุดยอดที่เข้าชมเป็น check[a] =true และเพิ่มไปที่ l1 โดยใช้ l1.push_back(a) และตั้งค่าระดับเป็น 0 arr[a] =0
• ในขณะที่คิว l1 ไม่ว่าง
• ใช้องค์ประกอบด้านหน้าเป็น a =l1 front() และพิมพ์โดยใช้ l1.pop_front().
• ทำเครื่องหมายจุดยอดที่ยังไม่ได้เยี่ยมชมที่อยู่ติดกันทั้งหมดของ a ว่าได้เข้าชมแล้ว และเพิ่มไปยังคิว l1
• กำหนดระดับของแต่ละจุดยอดที่อยู่ติดกันเป็นระดับ + 1
• ที่ส่วนท้ายของ while loop traverse arr[] โดยใช้ for loop และสำหรับแต่ละ arr[i] ==b นับการเพิ่มขึ้น
• เมื่อสิ้นสุดการส่งคืน นับเป็นผลลัพธ์

ตัวอย่าง

#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