एक अदिश ग्राफ दिया गया है जिसमें ट्री के नोड्स शीर्ष के रूप में हैं। लक्ष्य BFS (ब्रेडथ फर्स्ट सर्च) एल्गोरिदम का उपयोग करके ट्री के दिए गए स्तर पर नोड्स की संख्या ढूंढना है।
BFS एल्गोरिदम:-
यह एल्गोरिदम ग्राफ/ट्री को स्तर दर स्तर पार करना शुरू करता है। स्तर 0 पर नोड से शुरू करके, यह पहले स्तर 1 पर इससे सीधे जुड़े सभी नोड्स को पार करेगा, फिर अगले स्तर पर सभी नोड्स को पार करेगा और इसी तरह।
- वर्तमान स्तर पर नोड्स को क्षैतिज रूप से पार करें।
- अगले स्तर पर नोड्स को इसी तरह पार करें।
उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - level=2

आउटपुट - BFS का उपयोग करके ट्री में दिए गए स्तर पर नोड्स की संख्या: 1
व्याख्या - जैसा कि ऊपर दिखाया गया है ग्राफ में सभी स्तरों पर एक ही नोड है।
इनपुट - level=1

आउटपुट - BFS का उपयोग करके ट्री में दिए गए स्तर पर नोड्स की संख्या: 2
व्याख्या - जैसा कि ऊपर दिखाया गया है ग्राफ में सभी स्तरों पर एक ही नोड है। नोड्स 1, 2 हैं।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम प्रत्येक नोड को पार करेंगे और उनके स्तर को उनके पैरेंट से एक स्तर अधिक सेट करेंगे। हम एडजेसेंसी लिस्ट प्रतिनिधित्व का उपयोग करके ग्राफ को दर्शाएंगे।
यदि शुरुआती नोड 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

- डेटा के रूप में शीर्षों की संख्या और next के रूप में एडजेसेंसी लिस्ट के पॉइंटर के साथ ग्राफ का प्रतिनिधित्व करने वाला एक क्लास node बनाएं।
- पब्लिक मेथड insert(int val, int point) ग्राफ में एज जोड़ता है।
- यह val को point की एडजेसेंसी लिस्ट में और point को val की एडजेसेंसी लिस्ट में जोड़ता है।
- फ़ंक्शन count_nodes(int a, int b) स्रोत नोड a से शुरू होकर स्तर b पर नोड्स की संख्या लौटाता है।
- प्रारंभिक गिनती 0 सेट करें।
- bool सरणी check = new bool[data] लें।
- सरणी arr[data] ग्राफ के प्रत्येक शीर्ष का स्तर संग्रहीत करती है।
- for लूप का उपयोग करके ग्राफ के सभी शीर्षों को गैर-देखा गया सेट करें और check[i] = false और arr[i] = 0 सेट करें।
- BFS पारगमन के लिए एक कतार l1 बनाएं।
- शुरुआती शीर्ष को देखा गया चिह्नित करें check[a] = true और l1.push_back(a) का उपयोग करके इसे l1 में जोड़ें और इसका स्तर 0 सेट करें। arr[a] = 0।
- जब तक कतार l1 खाली नहीं है।
- सामने के तत्व को a = l1.front() के रूप में लें और l1.pop_front() का उपयोग करके इसे प्रिंट करें।
- a के सभी आसन्न अनदेखे शीर्षों को देखा गया चिह्नित करें और कतार l1 में जोड़ें।
- प्रत्येक आसन्न शीर्ष का स्तर a के स्तर + 1 के रूप में सेट करें।
- while लूप के अंत में for लूप का उपयोग करके arr[] को पार करें और प्रत्येक 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