กำหนดกราฟแบบไม่มีทิศทางที่มีโหนดของต้นไม้เป็นยอด (vertices) เป้าหมายคือหาจำนวนโหนดในระดับที่กำหนดของต้นไม้โดยใช้อัลกอริทึม BFS (Breadth First Search)
อัลกอริทึม BFS:-
อัลกอริทึมนี้เริ่มเดินทางผ่านกราฟ/ต้นไม้ทีละระดับ เริ่มจากโหนดที่ระดับ 0 จะเดินทางผ่านโหนดทั้งหมดที่เชื่อมต่อโดยตรงที่ระดับ 1 ก่อน แล้วจึงเดินทางผ่านโหนดทั้งหมดที่ระดับถัดไป และทำต่อไป
- เดินทางผ่านโหนดแนวนอนในระดับปัจจุบัน
- เดินทางผ่านโหนดในระดับถัดไปในลักษณะเดียวกัน
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - level = 2
Output - จำนวนโหนดในระดับที่กำหนดของต้นไม้ด้วย BFS คือ: 1
คำอธิบาย - ตามที่แสดงข้างต้น ทุกระดับมีโหนดเดียวในกราฟ
Input - level = 1
Output - จำนวนโหนดในระดับที่กำหนดของต้นไม้ด้วย BFS คือ: 2
คำอธิบาย - ตามที่แสดงข้างต้น ทุกระดับมีโหนดเดียวในกราฟ โหนดคือ 1, 2
แนวทางที่ใช้ในโปรแกรมด้านล่าง
ในแนวทางนี้ เราจะเดินทางผ่านแต่ละโหนดและตั้งระดับของพวกเขาเป็นระดับหนึ่งมากกว่าพ่อแม่ เราจะแสดงกราฟโดยใช้ adjacency list representation
ถ้าโหนดเริ่มต้นคือ 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 แสดงกราฟด้วยข้อมูลเป็นจำนวนยอดและ next เป็น pointer ไปยัง adjacency list
- Public method insert(int val, int point) เพิ่มขอบไปยังกราฟ
- เพิ่ม val เข้า adjacency list ของ point และ point เข้า adjacency list ของ val
- ฟังก์ชัน count_nodes(int a, int b) คืนค่าจำนวนโหนดที่ระดับ b เริ่มจากโหนดต้นทาง a
- ตั้งค่า count เริ่มต้นเป็น 0
- รับอาร์เรย์ bool check = new bool[data]
- อาร์เรย์ arr[data] เก็บระดับของแต่ละยอดของกราฟ
- ตั้งค่ายอดทั้งหมดของกราฟเป็นไม่ได้เยี่ยมชมด้วย for loop ตั้ง check[i] = false และ arr[i] = 0
- สร้างคิว l1 สำหรับการเดินทาง BFS
- ทำเครื่องหมายโหนดเริ่มต้นว่าเยี่ยมชมแล้ว check[a] = true และเพิ่มเข้า l1 ด้วย l1.push_back(a) ตั้งระดับเป็น 0 arr[a] = 0
- While คิว l1 ไม่ว่าง
- รับองค์ประกอบหน้าสุดเป็น a = l1.front() และพิมพ์ด้วย l1.pop_front()
- ทำเครื่องหมายยอดติดกันที่ยังไม่ได้เยี่ยมชมของ a ว่าเยี่ยมชมแล้วและเพิ่มเข้าคิว l1
- ตั้งระดับของแต่ละยอดติดกันเป็นระดับของ a + 1
- ในท้ายที่สุดของ while loop เดินทางผ่าน arr[] ด้วย for loop และสำหรับแต่ละ arr[i] == b เพิ่ม count
- ในที่สุดคืนค่า count เป็นผลลัพธ์
ตัวอย่าง
#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
