ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन ताल भारत जीई हेल्थकेयर Hasing.com पकेट रत्न UHG Optum
चौड़ाई पहिलो खोजी ग्राफ लाम

ब्रेडथ फर्स्ट सर्च (BFS) एउटा ग्राफको लागि रूख / ग्राफ डाटा संरचनामा ट्र्यार्सिंग वा खोजी एल्गोरिथ्म हो। यो दिइएको भेरटेक्स (कुनै पनि मनमानी शीर्ष) मा शुरू हुन्छ र सबै जडान भेरटेक्स को अन्वेषण गर्दछ र त्यसपछि नजिकको शीर्ष शीर्ष मा सर्छ र सबै अनपेक्षित नोडहरू अन्वेषण गर्दछ र ख्याल राख्दछ कि कुनै भेरटेक्स / नोडहरू दुई पटक भ्रमण गरिएको छैन। कुनै विशेष नोडबाट सुरु गरिएको ग्राफको BFS पत्ता लगाउन हामीलाई a लाम डाटा संरचना पत्ता लगाउन। यसको द्रुत समझका लागि उदाहरणमा सारौं

ब्रेडथ फर्स्ट सर्च (BFS) ट्रभर्सल र यसको कार्यान्वयन

जब हामी विशेष नोडमा जडान भएका नोडहरू थप्दछौं तब हामी त्यो नोडलाई पनि नतिजामा थप्छौं र प from्क्तिबाट प from्क्तिबाट थप बुझ्नको लागि केवल तलको चरण प्रक्रिया हेर्नुहोस्।

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

ग्राफको लागि ब्रेडथ फर्स्ट सर्च (BFS)

 

 

 

 

 

 

NOTE:

  •   त्यहाँ एक भन्दा बढी BFS सम्भव छ कुनै विशेष ग्राफको लागि (माथिको ग्राफ जस्तो)। माथिको ग्राफका लागि केहि अन्य सम्भावित BFS जस्तै: (१,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), (१, XNUMX)…।
  • BFS छ स्तर अर्डर ट्राभर्सल.

चौडाई पहिलो खोजी (BFS) को कार्यान्वयन

C ++ को चौडाई खोज (BFS) को लागी कोड

/*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

BFS को समय जटिलता

O (V + E) जहाँ V ले शिरोबिन्दुहरूको संख्या दर्शाउँछ र E किनारहरूको संख्या दर्शाउँछ।

संदर्भ

अन्तर्वार्ता प्रश्नहरू