आलेखासाठी ब्रेडथ फर्स्ट सर्च (बीएफएस)


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन कॅडन्स इंडिया जीई हेल्थकेअर गृहनिर्माण.कॉम पॉकेट रत्ने यूएचजी ऑप्टम
रुंदी प्रथम शोध आलेख रांग

ब्रेडथ फर्स्ट सर्च (बीएफएस) ग्राफसाठी वृक्ष / आलेख डेटा संरचनेत शोधणे किंवा शोधणे अल्गोरिदम आहे. हे एका शीर्ष शिरोबिंदूपासून सुरू होते (कोणतीही अनियंत्रित शिरोबिंदू) आणि सर्व कनेक्ट केलेल्या शिरोबिंदूचा शोध घेतो आणि त्यानंतर जवळच्या शिरोबिंदूकडे जाते आणि सर्व न सापडलेल्या गाठींचा शोध घेते आणि काळजी घेतली जाते की वर्टेक्स / नोड्स दोनदा भेट दिले नाहीत. एखाद्या विशिष्ट नोडपासून सुरू होणार्‍या ग्राफचा बीएफएस शोधण्यासाठी आम्हाला आवश्यक आहे रांग डेटा संरचना शोधण्यासाठी. च्या द्रुत समजून घेण्यासाठी उदाहरणाकडे जाऊया

ब्रेडथ फर्स्ट सर्च (बीएफएस) ट्रव्हर्सल आणि त्याची अंमलबजावणी

जेव्हा आम्ही एखाद्या विशिष्ट नोडमध्ये जोडलेले नोड जोडतो तेव्हा आम्ही त्या नोडला परिणामामध्ये जोडतो आणि अधिक समजून घेण्यासाठी रांगेतून खाली पलीकडे खाली चरण कार्यपद्धती पाहतो:

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

आलेखासाठी रूंदी प्रथम शोध (बीएफएस)

 

 

 

 

 

 

सुचना:

  •   एका विशिष्ट आलेखासाठी (वरील आलेखाप्रमाणे) एकापेक्षा जास्त बीएफएस शक्य आहेत. वरील आलेखासाठी इतर काही संभाव्य बीएफएस प्रमाणेः (1,3,2,5,6,7,4,8), (1,3,2,7,6,5,4,8), (1,3,2,6,7,5,4,8, XNUMX)….
  • बीएफएस आहे पातळी ऑर्डर आडवा.

रुंदी प्रथम शोध (बीएफएस) ची अंमलबजावणी

ब्रेडथ फर्स्ट सर्च (बीएफएस) साठी सी ++ कोड

/*C++ Implementation of BFS of a given graph using STL*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    /*take input*/
    cin>>nodes>>edges;
    vector<int> v[nodes+1];
    bool visited[nodes+1];
    memset(visited,false,sizeof(visited));
    /*Make graph using vector*/
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        /*add edge between x and y*/
        v[x].push_back(y);
        /*add edge between y and x*/
        v[y].push_back(x);
    }
    int start;
    /*Take input node at which the BFS starts*/
    cin>>start;
    queue<int> q_calc;
    q_calc.push(start);
    visited[start]=true;
    vector<int> bfs;
    while(!q_calc.empty())
    {
        /*pop the element from queue*/
        int pop_elem=q_calc.front();
        /*update the answer*/  
        bfs.push_back(pop_elem);
        q_calc.pop();
        /*add all the connected nodes with pop_elem into queue*/
        for(int i=0;i<v[pop_elem].size();i++)
        {
            /*if we visit already then we can't add it into queue*/
            if(!visited[v[pop_elem][i]])
            {
                visited[v[pop_elem][i]]=true;
                q_calc.push(v[pop_elem][i]);
            }
        }
    }
    /*print the BFS for given graph at starting with given node*/
    for(int i=0;i<nodes;i++)
    {
        cout<<bfs[i]<<" ";
    }
    cout<<"\n";
  return 0;
}
Input:
8 9
1 2
1 3
2 4
3 4
3 5
3 6
3 7
6 8
7 8
1
Output:
1 2 3 4 5 6 7 8

बीएफएसची वेळ कॉम्प्लेक्सिटी

ओ (व्ही + ई) जेथे व्ही शिरोबिंदू संख्या दर्शविते आणि ई कडा संख्या दर्शवितो.

संदर्भ

मुलाखत प्रश्न