Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में BFS का उपयोग करके ट्री में दिए गए स्तर पर नोड्स की संख्या गिनना


एक अदिश ग्राफ दिया गया है जिसमें ट्री के नोड्स शीर्ष के रूप में हैं। लक्ष्य BFS (ब्रेडथ फर्स्ट सर्च) एल्गोरिदम का उपयोग करके ट्री के दिए गए स्तर पर नोड्स की संख्या ढूंढना है।

BFS एल्गोरिदम:-

यह एल्गोरिदम ग्राफ/ट्री को स्तर दर स्तर पार करना शुरू करता है। स्तर 0 पर नोड से शुरू करके, यह पहले स्तर 1 पर इससे सीधे जुड़े सभी नोड्स को पार करेगा, फिर अगले स्तर पर सभी नोड्स को पार करेगा और इसी तरह।

  • वर्तमान स्तर पर नोड्स को क्षैतिज रूप से पार करें।
  • अगले स्तर पर नोड्स को इसी तरह पार करें।

उदाहरणों से समझते हैं।

उदाहरण के लिए

इनपुट - level=2

C++ में BFS का उपयोग करके ट्री में दिए गए स्तर पर नोड्स की संख्या गिनना

आउटपुट - BFS का उपयोग करके ट्री में दिए गए स्तर पर नोड्स की संख्या: 1

व्याख्या - जैसा कि ऊपर दिखाया गया है ग्राफ में सभी स्तरों पर एक ही नोड है। 

इनपुट - level=1

C++ में BFS का उपयोग करके ट्री में दिए गए स्तर पर नोड्स की संख्या गिनना

आउटपुट - 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

C++ में BFS का उपयोग करके ट्री में दिए गए स्तर पर नोड्स की संख्या गिनना

  • डेटा के रूप में शीर्षों की संख्या और 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

  1. OpenCV में C++ का उपयोग करके चेहरों की संख्या गिनें OpenCV में C++ का उपयोग करके चेहरों की संख्या गिनें

    छवि में स्थित चेहरों की संख्या गिनना आसान है। पिछले अनुभाग में हमने जो प्रोग्राम लिखा था, उसमें पहले से ही faces.size() में चेहरों की संख्या की जानकारी है। यह कोड faces.size() एक पूर्णांक मान देता है।उदाहरण के लिए, यदि हम int x = faces.size() लिखते हैं, तो x में चेहरों की संख्या होगी।दिए गए छवि से च

  1. - C++ का उपयोग करके किसी संख्या में दी गई स्थिति या इंडेक्स पर बिट को अपडेट करें

    दिए गए प्रॉब्लम में, हमें किसी संख्या के दिए गए इंडेक्स के बिट को अपडेट करना है। संख्या को अपडेट करने के लिए, हम दी गई संख्या पर बिट मैनिपुलेशन ऑपरेशन का उपयोग कर सकते हैं। उदाहरण के लिए, इनपुट-1 - N = 25, बिट = 1, पोजीशन = 2 आउटपुट - 29 व्याख्या - चूंकि दिया गया इनपुट 25 को बाइनरी में 11001 के रूप

  1. C++ में दिए गए ट्री में उन नोड्स को गिनना जिनका वजन दो की घात है C++ में दिए गए ट्री में उन नोड्स को गिनना जिनका वजन दो की घात है

    नोड्स के वजन वाली एक बाइनरी ट्री दी गई है। लक्ष्य उन नोड्स की संख्या ढूंढना है जिनके वजन ऐसे हैं कि संख्या दो की घात है। यदि वजन 32 है तो यह 2⁵ है इसलिए यह नोड गिना जाएगा। उदाहरण के लिए इनपुट मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है: आउटपुट Count the nodes in the given tree whos