Шырыня першага пошуку (BFS) для графіка  


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Cadence Індыя 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 - колькасць кантаў.

Глядзіце таксама
Максімальная плошча выспы

Спасылка

Інтэрв'ю Пытанні