जंगल के शीर्षों को देखते हुए (पेड़ों का संग्रह)। लक्ष्य उस जंगल में पेड़ों की संख्या ज्ञात करना है। हम जंगल पर DFS (गहराई से पहली खोज) एल्गोरिथम चलाकर ऐसा करेंगे।
उदाहरण के लिए
इनपुट
edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} } आउटपुट
Count of number of trees in a forest are: 3
स्पष्टीकरण
जंगल में मौजूद पेड़ों की संख्या है -
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम पुनरावर्ती रूप से ग्राफ़ पर डेप्थ फ़र्स्ट सर्च एल्गोरिथम लागू करते हैं। यदि प्रत्येक कनेक्टेड नोड को एक स्रोत से विज़िट किया गया चिह्नित किया जाता है (जिसका अर्थ है कि एक पेड़ बनता है) तो हम गिनती बढ़ाएंगे।
-
ग्राफ़ पर एक पूर्णांक शीर्ष को कई शीर्षों के रूप में लें।
-
शीर्षों को पूर्णांकों के रूप में संग्रहीत करने के लिए एक सदिश वेक्टर
vec[vertice] लें। -
फ़ंक्शन डालने (वेक्टर
vec [], int माता-पिता, int बच्चा) vec [] लेता है और उस वेक्टर में नोड्स माता-पिता और बच्चे के बीच एक किनारे जोड़ता है। -
vec[parent].push_back(child) और vec[child].push_back(parent) का उपयोग करके बढ़त जोड़ें।
-
फंक्शन रिकर्ड (int temp, वेक्टर
vec[], vector &check) वर्टेक्स टेम्परेचर से ग्राफ पर DFS लागू करता है। -
ऐरे चेक [अस्थायी] का उपयोग सही/गलत का उपयोग करके नोड्स को विज़िट/अनविजिट के रूप में सेट करने के लिए किया जाता है।
-
ट्रैवर्स वेक्टर vec[] लूप के लिए उपयोग कर रहा है और यदि check[vec[temp][i]] गलत है तो कॉलरेक्रर्ड (vec[temp][i], vec, check) कनेक्टेड नोड्स के लिए पुनरावर्ती रूप से करें।
-
फ़ंक्शन Trees_Forest(vector
vec[], int vertice) vec[] लेता है और vec[] में आसन्न सूची के रूप में दिए गए जंगल में पेड़ों की गिनती देता है। -
वनों की प्रारंभिक गणना 0 के रूप में लें।
-
ग्राफ़ के शीर्षों को विज़िट किए गए के रूप में चिह्नित करने के लिए वेक्टर<बूल> चेक(वर्टिस, असत्य) लें।
-
लूप के लिए उपयोग करके सभी शीर्षों को ट्रैवर्स करें।
-
अगर चेक [i] गलत है तो रिकर्ड (i, vec, check) और इंक्रीमेंटकाउंट का उपयोग करके dfs लागू करें।
-
सभी लूपों के अंत में परिणाम के रूप में वापसी की गणना करें।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
void insert(vector<int> vec[], int parent, int child){
vec[parent].push_back(child);
vec[child].push_back(parent);
}
void recurred(int temp, vector<int> vec[], vector<bool> &check){
check[temp] = true;
int size = vec[temp].size();
for(int i = 0; i < size; i++){
if (check[vec[temp][i]] == false){
recurred(vec[temp][i], vec, check);
}
}
}
int Trees_Forest(vector<int> vec[], int vertice){
int count = 0;
vector<bool> check(vertice, false);
for(int i = 0; i < vertice; i++){
if(check[i] == false){
recurred(i, vec, check);
count++;
}
}
return count;
}
int main(){
int vertice = 9;
vector<int> vec[vertice];
insert(vec, 1, 3);
insert(vec, 2, 8);
insert(vec, 2, 6);
insert(vec, 3, 5);
insert(vec, 3, 7);
insert(vec, 4, 8);
cout<<"Count of number of trees in a forest are: "<<Trees_Forest(vec, vertice);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of number of trees in a forest are: 3