Bir qrafik üçün genişlik ilk axtarış (BFS)

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Cadence Hindistan GE Healthcare mənzil.com Cib daşları UHG Optum
Genişlik İlk Axtarış Qrafik QueueBaxılıb 27

Genişlik İlk Axtarış (BFS) qraf üçün ağac / qrafika məlumat strukturunda keçid və axtarış alqoritmidir. Verilən bir təpədən başlayır (hər hansı bir ixtiyari təpə) və əlaqəli bütün təpəni araşdırır və bundan sonra ən yaxın təpəyə doğru hərəkət edir və tədqiq edilməmiş bütün qovşaqları araşdırır və heç bir təpə / düyünün iki dəfə ziyarət edilməməsinə diqqət yetirir. Müəyyən bir qovşaqdan başlayaraq verilmiş bir qrafikin BFS-sini tapmaq üçün a Queue məlumat quruluşunu tapmaq. Bunu tez başa düşmək üçün nümunəyə keçək

Genişlik Birinci Axtarış (BFS) keçidi və tətbiqi

Bağlı düyünləri müəyyən bir düyünə əlavə etdikdə nəticəni də əlavə edirik və daha çox anlaşma üçün növbədən yalnız aşağıdakı prosedur proseduruna baxın:

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Bir qrafik üçün genişlik ilk axtarış (BFS)Pin

 

Pin

 

Pin

 

Pin

 

Pin

 

Pin

 

QEYD:

  •   Müəyyən bir qrafik üçün birdən çox BFS mümkündür (yuxarıdakı qrafik kimi). Yuxarıdakı qrafik üçün bəzi digər mümkün BFS-lər kimi: (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 edir səviyyə sifarişinin kəsişməsi.

Genişlik İlk Axtarışının (BFS) tətbiqi

Genişlik İlk Axtarış üçün C ++ Kodu (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-nin Zaman Mürəkkəbliyi

O (V + E), burada V təpələrin sayını, E isə kənarların sayını göstərir.

arayış

Müsahibə Suallar

Translate »