Широчина първо търсене (BFS) за графика


Ниво на трудност Лесно
Често задавани в Амазонка Каденс Индия GE Healthcare Housing.com Джобни скъпоценни камъни UHG Optum
Широчина Първо търсене Крива Опашка

Широчина първо търсене (BFS) за графика е алгоритъм за обхождане или търсене в структурата на данни дърво / графика. Започва от даден връх (произволен произволен връх) и изследва всички свързани върхове и след това се придвижва до най-близкия връх и изследва всички неизследвани възли и се грижи нито един връх / възли да не са посетени два пъти. За да открием BFS на дадена графика, започвайки от определен възел, ни трябва a Опашка структура на данните, за да разберете. Нека да преминем към примера за бързо разбиране на

Обход за първо търсене на широчина (BFS) и неговото прилагане

Когато добавяме свързани възли към определен възел, ние също добавяме този възел към резултата и го изваждаме от опашката за повече разбиране, просто вижте процедурата по стъпка по-долу:

Широчина първо търсене (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 означава броят на ръбовете.

препратка

Въпроси за интервю