BFS ব্যবহার করে ট্রিতে নির্দিষ্ট লেভেলের নোড সংখ্যা গণনা (C++)

একটি অনায়াক্ত গ্রাফ দেওয়া আছে যাতে ট্রির নোডগুলো ভার্টেক্স হিসেবে রয়েছে। লক্ষ্য হল BFS (Breadth First Search) অ্যালগরিদম ব্যবহার করে ট্রির নির্দিষ্ট লেভেলের নোড সংখ্যা বের করা।

BFS অ্যালগরিদম: এই অ্যালগরিদম গ্রাফ/ট্রি লেভেল বাই লেভেল ট্রাভার্স করে। লেভেল ০-র নোড থেকে শুরু করে লেভেল ১-এ সরাসরি সংযুক্ত নোডগুলো ট্রাভার্স করে, তারপর লেভেল ২, ৩... ইত্যাদি।

• কারেন্ট লেভেলের নোডগুলো হরিজেন্টালি ট্রাভার্স করুন।
• পরবর্তী লেভেলের নোডগুলো একইভাবে ট্রাভার্স করুন।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট - level=2

আউটপুট - BFS ব্যবহার করে নির্দিষ্ট লেভেলের নোড সংখ্যা: ১

ব্যাখ্যা - দেখানো অনুযায়ী সব লেভেলে একক নোড রয়েছে।

ইনপুট - level=1

আউটপুট - BFS ব্যবহার করে নির্দিষ্ট লেভেলের নোড সংখ্যা: ২

ব্যাখ্যা - দেখানো অনুযায়ী লেভেল ১-এ নোড ১, ২ রয়েছে।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

এই পদ্ধতিতে প্রতিটি নোড ট্রাভার্স করে তাদের লেভেল প্যারেন্টের চেয়ে এক লেভেল বেশি সেট করা হয়। গ্রাফকে এডজেসেন্সি লিস্ট রিপ্রেজেন্টেশন দিয়ে প্রকাশ করা হয়।

যদি স্টার্টিং নোড ০ হয়:

• 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 = এডজেসেন্সি লিস্ট পয়েন্টার)।
• পাবলিক মেথড insert(int val, int point) এডজেসেন্সি লিস্টে এজ যোগ করে।
• ফাংশন count_nodes(int a, int b) সোর্স নোড a থেকে লেভেল b-এ নোড সংখ্যা রিটার্ন করে।
• প্রাথমিক কাউন্ট ০।
• বুল অ্যারে check = new bool[data]।
• অ্যারে arr[data] প্রতিটি ভার্টেক্সের লেভেল সংরক্ষণ করে।
• ফর লুপে সব ভার্টেক্স নন-ভিজিটেড সেট করুন (check[i]=false, arr[i]=0)।
• BFS ট্রাভার্সালের জন্য কিউ l1 তৈরি করুন।
• স্টার্টিং ভার্টেক্স ভিজিটেড মার্ক করুন (check[a]=true), কিউতে পুশ করুন (l1.push_back(a)), লেভেল ০ সেট করুন (arr[a]=0)।
• যখন কিউ খালি নয়:
  • ফ্রন্ট এলিমেন্ট a = l1.front(), পপ করুন (l1.pop_front())।
  • a-র সব এডজেসেন্ট অনভিজিটেড ভার্টেক্স ভিজিটেড মার্ক করুন, কিউতে পুশ করুন।
  • প্রতিটি এডজেসেন্ট ভার্টেক্সের লেভেল = arr[a] + 1।
• হোয়াইল লুপ শেষে arr[] ট্রাভার্স করে 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