एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना ताल भारत जीई हेल्थकेयर Housing.com पॉकेट रत्न यूएचजी ऑप्टम
पहले चौड़ाई खोजो ग्राफ पंक्ति

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

चौड़ाई प्रथम खोज (BFS) ट्रैवर्सल और इसका कार्यान्वयन

जब हम किसी विशेष नोड से जुड़े नोड्स को जोड़ते हैं, तो हम उस नोड को परिणाम और पॉप में भी जोड़ते हैं, जो कतार से अधिक समझ के लिए नीचे चरण प्रक्रिया द्वारा बस देखते हैं:

एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)

 

एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)

 

एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)

 

एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)

 

एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)

 

एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)

 

एक ग्राफ के लिए चौड़ाई पहली खोज (BFS)

 

एक ग्राफ के लिए चौड़ाई पहली खोज (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)…।
  • 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 किनारों की संख्या को दर्शाता है।

संदर्भ

साक्षात्कार के प्रश्न