幅優先検索 (BFS)
BFS (幅優先検索、
幅優先検索) - 単純なアルゴリズムと高度なアルゴリズムの両方でよく使用されるグラフ走査手法。幅優先検索は、ソース ノードから開始して徐々にソース ノードから離れていき、グラフの個々のレベルを段階的に実行することによって機能します。これはアニメーションで明確に示されています。
最も単純な BFS を記述するには、最初から取得して最後まで配置できるデータ構造を操作でき、また保存できる必要があります。隣接リストの形式のグラフ (つまり、キュー付き)。
アルゴリズムの正式な説明
1) 検索を開始する頂点の番号を最初は空のキューに入れます。
2) キューの先頭から頂点 U を抽出し、別の配列で使用されるものとしてマークします。
3) キューの最後に、頂点 U, からのエッジを使用して到達でき、まだラベルが付けられていないすべての頂点を追加します。
4) キューが空の場合は、接続されたグラフのすべてのノードがスキャンされています。そうでない場合は、ステップ 2 に戻ります。
複雑さ
アルゴリズムは最悪の場合グラフのすべてのノードを訪問するため、グラフを隣接リストとして保存する場合、アルゴリズムの時間計算量は O(|V| + |E|) になります。ここで、 V はグラフの頂点のセット、E はエッジのセットです。言い換えると、アルゴリズムは number の最悪のケースでも機能します。エッジの数 + 頂点の数.