एक अप्रत्यक्ष ग्राफ दिया गया है जिसमें एक पेड़ के नोड्स को शिखर के रूप में रखा गया है। लक्ष्य बीएफएस (चौड़ाई पहली खोज) एल्गोरिदम का उपयोग करके पेड़ के दिए गए स्तर पर नोड्स की गिनती का पता लगाना है।
बीएफएस एल्गोरिथम:-
यह एल्गोरिथम ग्राफ/पेड़ स्तर को स्तर से पार करना शुरू कर देता है। स्तर 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
- एक ऐसा वर्ग नोड बनाएं जो ग्राफ़ को शीर्षों की संख्या के रूप में और उसके बाद आसन्न सूची के सूचक के रूप में दर्शाए।
- पब्लिक मेथड इंसर्ट (इंट वैल, इंट पॉइंट) ग्राफ में बढ़त जोड़ता है।
- यह बिंदु की आसन्नता सूची में वैल जोड़ता है और वैल की आसन्नता सूची को इंगित करता है।
- फ़ंक्शन काउंट_नोड्स (इंट ए, इंट बी) सोर्स नोड ए से शुरू करके लेवल बी पर नोड्स की गिनती देता है।
- प्रारंभिक गणना को 0 के रूप में सेट करें।
- बूल सरणी जांच लें =नया बूल[डेटा]।
- ऐरे एआर [डेटा] ग्राफ़ के प्रत्येक शीर्ष के स्तर को संग्रहीत करता है।
- लूप के लिए उपयोग करके ग्राफ़ के सभी शीर्षों को गैर-विज़िट के रूप में सेट करें और चेक[i] =असत्य और arr[i] =0 सेट करें।
- बीएफएस ट्रैवर्सल के लिए एक कतार l1 बनाएं।
- चेक के रूप में देखे गए शीर्ष को चिह्नित करें[a] =true और l1.push_back(a) का उपयोग करके इसे l1 में जोड़ें और इसका स्तर 0 के रूप में सेट करें। arr[a] =0.
- जबकि कतार l1 खाली नहीं है।
- सामने वाले तत्व को a =l1 के रूप में लें। front() और l1.pop_front() का उपयोग करके इसे प्रिंट करें।
- ए के सभी आसन्न न देखे गए शीर्षों को विज़िट किया गया के रूप में चिह्नित करें और कतार l1 में जोड़ें।
- प्रत्येक आसन्न शीर्ष के स्तर को + 1 के स्तर के रूप में सेट करें।
- जबकि लूप ट्रैवर्स एआर के अंत में [] लूप के लिए और प्रत्येक एआर के लिए [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