กำหนดกราฟแบบไม่มีทิศทางที่มีโหนดของต้นไม้เป็นยอด เป้าหมายคือการค้นหาจำนวนโหนดที่ระดับที่กำหนดของทรีโดยใช้อัลกอริธึม 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
