グラフの幅優先探索(BFS)


難易度 簡単に
よく聞かれる Amazon (アマゾン) ケイデンスインド GEヘルスケア Housing.com ポケットジェム UHGオプタム
幅優先探索 グラフ キュー

幅優先探索(BFS) グラフの場合は、ツリー/グラフデータ構造のトラバースまたは検索アルゴリズムです。 特定の頂点(任意の頂点)から開始し、接続されているすべての頂点を探索し、その後、最も近い頂点に移動して、探索されていないすべてのノードを探索し、XNUMX回アクセスした頂点がないように注意します。 特定のノードから始まる特定のグラフのBFSを見つけるには、 キュー 調べるためのデータ構造。 例に移って、

幅優先探索(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)の実装

幅優先探索(BFS)のC ++コード

/*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はエッジの数を示します。

参照

面接の質問